Stabbing Circles for Sets of Segments in the Plane

0478948 - ÚI 2018 US eng J - Journal Article
Claverol, M. - Khramtcova, E. - Papadopoulou, E. - Saumell, Maria - Seara, C.
Stabbing Circles for Sets of Segments in the Plane.
Algorithmica. Roč. 80, č. 3 (2018), s. 849-884. ISSN 0178-4617. E-ISSN 1432-0541
Keywords : Cluster Voronoi diagrams * Farthest-color Voronoi diagram * Hausdorff Voronoi diagram * Stabbing circle * Stabbing line segments * Voronoi diagram
Subject RIV: BA - General Mathematics
Impact factor: 0.882, year: 2018

Stabbing a set S of n segments in the plane by a line is a well-known problem. In this paper we consider the variation where the stabbing object is a circle instead of a line. We show that the problem is tightly connected to two cluster Voronoi diagrams, in particular, the Hausdorff and the farthest-color Voronoi diagram. Based on these diagrams, we provide a method to compute a representation of all the combinatorially different stabbing circles for S, and the stabbing circles with maximum and minimum radius. We give conditions under which our method is fast. These conditions are satisfied if the segments in S are parallel, resulting in a (Formula presented.) time and O(n) space algorithm. We also observe that the stabbing circle problem for S can be solved in worst-case optimal (Formula presented.) time and space by reducing the problem to computing the stabbing planes for a set of segments in 3D. Finally we show that the problem of computing the stabbing circle of minimum radius for a set of n parallel segments of equal length has an (Formula presented.) lower bound.
Permanent Link: http://hdl.handle.net/11104/0274989