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
Presentation of work at congresses
Name of edition
XVI Spanish Meeting on Computational Geometry
Date of publication
2015
Presentation's date
2015-07-03
Book of congress proceedings
XVI Spanish meeting of computational geometry: Barcelona : July 1-3, 2015: proceedings book
First page
93
Last page
96
Project funding
MINECO MTM2012-30951
Repository
http://www-ma2.upc.es/egc15/wp-content/uploads/2013/10/AbstractsXVIEGC.pdf Open in new window
Abstract
We consider stabbing regions for a set S of n line segments in the plane, defined as regions that contain exactly one endpoint of each segment of S. We provide efficient algorithms that report all combinatorially different stabbing regions for S when the regions are described as the intersection of isothetic halfplanes: halfplanes, strips, quadrants, 3-sided rectangles, and rectangles. The running times are O(n) (for the halfplane case), O(n log n) (for strips, quadrants, and 3-sided rectangles)...
Keywords
3-sided rectangles, Stabbing regions, classification, line segments, quadrants, rectangles., separability, strips
Group of research
CGA -Computational Geometry and Applications

Participants