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
Journal article
Journal
Applied mathematics and computation
Date of publication
2017-09-15
Volume
309
First page
359
Last page
373
DOI
https://doi.org/10.1016/j.amc.2017.04.001 Open in new window
Repository
http://hdl.handle.net/2117/104941 Open in new window
URL
http://www.sciencedirect.com/science/article/pii/S0096300317302369 Open in new window
Abstract
Given a set S of n line segments in the plane, we say that a region R¿R2 is a stabber for S if R contains exactly one endpoint of each segment of S. In this paper we provide optimal or near-optimal algorithms for reporting all combinatorially different stabbers for several shapes of stabbers. Specifically, we consider the case in which the stabber can be described as the intersection of axis-parallel halfplanes (thus the stabbers are halfplanes, strips, quadrants, 3-sided rectangles, or rec...
Citation
Claverol, M., Garijo, D., Korman, M., Seara, C., Silveira, R.I. Stabbing segments with rectilinear objects. "Applied mathematics and computation", 15 Setembre 2017, vol. 309, p. 359-373.
Keywords
Algorithms, Classification problems, Computational geometry, Line segments, Stabbing problems
Group of research
CGA -Computational Geometry and Applications

Participants

Attachments