Let S be a set of n segments in the plane such that, for
every segment, its two endpoints are adjacent in the Delaunay triangulation of the set of endpoints of all segments in S. Our goal is to compute all the combinatorially different stabbing circles for S, and the ones with maximum and minimum radius. We exploit a recent result to solve this problem in O(n log n) in two particular cases: (i) all segments in S are parallel; (ii) all segments in S have the same length. We also show that the pro...
Let S be a set of n segments in the plane such that, for
every segment, its two endpoints are adjacent in the Delaunay triangulation of the set of endpoints of all segments in S. Our goal is to compute all the combinatorially different stabbing circles for S, and the ones with maximum and minimum radius. We exploit a recent result to solve this problem in O(n log n) in two particular cases: (i) all segments in S are parallel; (ii) all segments in S have the same length. We also show that the problem of computing the stabbing circle of minimum radius of a set of n parallel segments of equal length (not necessarily satisfying the Delaunay condition) has an Omega(n log n) lower bound.
Citation
Claverol, M., Khramtcova, E., Papadopoulou, E., Saumell, M., Seara, C. Stabbing circles for some sets of Delaunay segments. A: European Workshop on Computational Geometry. "EuroCG 2016: 32nd European Workshop on Computational Geometry March 30 – April 1, 2016 Book of Abstracts". Lugano: 2016, p. 139-142.