Stabbing segments with rectilinear objects
Visualitza/Obre
Cita com:
hdl:2117/104941
Tipus de documentArticle
Data publicació2017-09-15
Condicions d'accésAccés obert
Tots els drets reservats. Aquesta obra està protegida pels drets de propietat intel·lectual i
industrial corresponents. Sense perjudici de les exempcions legals existents, queda prohibida la seva
reproducció, distribució, comunicació pública o transformació sense l'autorització del titular dels drets
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 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).
Citació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.
ISSN0096-3003
Versió de l'editorhttp://www.sciencedirect.com/science/article/pii/S0096300317302369
Fitxers | Descripció | Mida | Format | Visualitza |
---|---|---|---|---|
jf-stab-rectangle-journal-final.pdf | Versión postprint | 382,3Kb | Visualitza/Obre |