TY - JOUR

T1 - Stabbing segments with rectilinear objects

AU - Claverol, Mercè

AU - Garijo, Delia

AU - Korman, Matias

AU - Seara, Carlos

AU - Silveira, Rodrigo I.

N1 - Funding Information:
M. C., C. S., and R.I. S. were partially supported by projects MINECO MTM2015-63791-R/FEDER and Gen. Cat. DGR2014SGR46. D. G. was supported by projects PAI FQM-0164 and MTM2014-60127-P. M. K. was supported in part by KAKENHI Nos. 12H00855 and 17K12635. R.I. S. was also partially supported by MINECO through the Ramón y Cajal program.
Publisher Copyright:
© 2017 Elsevier Inc.

PY - 2017/9/15

Y1 - 2017/9/15

N2 - 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 rectangles). The running times are O(n) (for the halfplane case), O(nlog n) (for strips, quadrants, and 3-sided rectangles), and O(n2log n) (for rectangles).

AB - 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 rectangles). The running times are O(n) (for the halfplane case), O(nlog n) (for strips, quadrants, and 3-sided rectangles), and O(n2log n) (for rectangles).

KW - Algorithms

KW - Classification problems

KW - Computational geometry

KW - Line segments

KW - Stabbing problems

UR - http://www.scopus.com/inward/record.url?scp=85018860048&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85018860048&partnerID=8YFLogxK

U2 - 10.1016/j.amc.2017.04.001

DO - 10.1016/j.amc.2017.04.001

M3 - Article

AN - SCOPUS:85018860048

SN - 0096-3003

VL - 309

SP - 359

EP - 373

JO - Applied Mathematics and Computation

JF - Applied Mathematics and Computation

ER -