.png){kind=icon}
.png){kind=icon}
Return
Stabbing segments with rectilinear objects
.png){kind=icon}
OA
AI
DOI：10.1016/j.amc.2017.04.001.png)
.png){kind=icon}
.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Given a set S of n line segments in the plane, we say that a region R subset of 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 areO(n) (for the halfplane case), O(nlogn) (for strips, quadrants, and 3-sided rectangles), and O(n(2)logn) (for rectangles). (C) 2017 Elsevier Inc. All rights reserved.
Keywords:
Computational geometry
Algorithms
Line segments
Stabbing problems
Classification problems
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
3.4
Papers:
2.3W
Citations:
3.3W
Organization
View more organizations