Back to Search
Start Over
Stabbing segments with rectilinear objects.
- Source :
-
Applied Mathematics & Computation . Sep2017, Vol. 309, p359-373. 15p. - Publication Year :
- 2017
-
Abstract
- Given a set S of n line segments in the plane, we say that a region R ⊆ R 2 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 rectangles). The running times are O ( n ) (for the halfplane case), O ( n log n ) (for strips, quadrants, and 3-sided rectangles), and O ( n 2 log n ) (for rectangles). [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 00963003
- Volume :
- 309
- Database :
- Academic Search Index
- Journal :
- Applied Mathematics & Computation
- Publication Type :
- Academic Journal
- Accession number :
- 122881573
- Full Text :
- https://doi.org/10.1016/j.amc.2017.04.001