Stabbing segments with rectilinear objects

Mercè Claverol, Delia Garijo, Matias Korman, Carlos Seara and Rodrigo I. Silveira

Applied Mathematics and Computation, 2017, vol. 309, issue C, 359-373

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).

Keywords: Computational geometry; Algorithms; Line segments; Stabbing problems; Classification problems (search for similar items in EconPapers)
Date: 2017
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0096300317302369
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:apmaco:v:309:y:2017:i:c:p:359-373

DOI: 10.1016/j.amc.2017.04.001

Access Statistics for this article

Applied Mathematics and Computation is currently edited by Theodore Simos

More articles in Applied Mathematics and Computation from Elsevier
Bibliographic data for series maintained by Catherine Liu ().