To access the full text documents, please follow this link: http://hdl.handle.net/2117/104128

Stabbing circles for sets of segments in the plane
Claverol Aguas, Mercè; Khramtcova, Elena; Papadopoulou, Evanthia; Saumell, Maria; Seara Ojea, Carlos
Universitat Politècnica de Catalunya. Departament de Matemàtiques; Universitat Politècnica de Catalunya. DCCG - Grup de recerca en geometria computacional, combinatoria i discreta
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 O(nlog2n) time and O(n) space algorithm. We also observe that the stabbing circle problem for S can be solved in worst-case optimal O(n2) 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 O(nlogn) lower bound.
Àrees temàtiques de la UPC::Informàtica
Àrees temàtiques de la UPC::Matemàtiques i estadística
Voronoi polygons
Stabbing circle
Stabbing line segments
Voronoi diagram
Cluster Voronoi diagrams
Hausdorff Voronoi diagram
Farthest-color Voronoi diagram
Geometria computacional
Article - Draft
Article
         

Show full item record

Related documents

Other documents of the same author

Claverol Aguas, Mercè; Khramtcova, Elena; Papadopoulou, Evanthia; Saumell, Maria; Seara Ojea, Carlos
Claverol Aguas, Mercè; Khramtcova, Elena; Papadopoulou, Evanthia; Saumell, Maria; Seara Ojea, Carlos
Claverol Aguas, Mercè; Garijo, Delia; Grima, Clara; Márquez, Alberto; Seara Ojea, Carlos
Claverol Aguas, Mercè; Garijo Royo, Delia; Korman, Matias; Seara Ojea, Carlos; Silveira, Rodrigo Ignacio
Claverol Aguas, Mercè; Garijo, Delia; Hurtado Díaz, Fernando Alfredo; Lara Cuevas, María Dolores; Seara Ojea, Carlos
 

Coordination

 

Supporters