Loading...
Loading...

Go to the content (press return)

Stabbing segments with rectilinear objects

Author
Claverol, M.; Garijo, D.; Korman, M.; Seara, C.; Silveira, R.
Type of activity
Book chapter
Book
Fundamentals of Computation Theory · Volume 9210 of the series Lecture Notes in Computer Science
First page
53
Last page
64
Date of publication
2015-08-17
ISBN
978-3-319-22176-2 Open in new window
DOI
https://doi.org/10.1007/978-3-319-22177-9 Open in new window
Repository
http://hdl.handle.net/2117/82298 Open in new window
Abstract
We consider stabbing regions for a set S of n line segments in the plane, that is, regions in the plane that contain exactly one endpoint of each segment of S. Concretely, we provide efficient algorithms for reporting all combinatorially different stabbing regions for S for regions that can be described as the intersection of axis-parallel halfplanes; these are halfplanes, strips, quadrants, 3-sided rectangles, and rectangles. The running times are O(n) (for the halfplane case), O(n log n) (for ...
Citation
Claverol, M., Garijo, D., Korman, M., Seara, C., Silveira, R.I. Stabbing segments with rectilinear objects. A: "Fundamentals of Computation Theory · Volume 9210 of the series Lecture Notes in Computer Science". 2015, p. 53-64.
Keywords
Rectilinear objects, Segments, Stabbing
Group of research
CGA -Computational Geometry and Applications

Participants