Stabbing circles and cluster Voronoi diagrams
Elena Khramtsova
University of Lugano

Let $S$ be a set of $n$ line segments in the plane. Stabbing $S$ by a line is a very well-known problem in computational geometry. But what if we want to stab it by a circle, rather than a line? We consider the stabbing circle problem: compute all the combinatorially different stabbing circles for $S$, and the stabbing circles with maximum and minimum radius. The problem is tightly connected to cluster Voronoi diagrams, in particular, the Hausdorff and the farthest-color Voronoi diagram, and this implies a method to solve the problem. We give conditions under which our method is fast. If all segments in $S$ are parallel, our method results in a $O(n \log^2 n)$ time algorithm. If all segments in $S$ are edges of a Delaunay triangualtion of some point set, and are either parallel, or have same length, the time complexity is optimal $O(n \log n)$.

In addition, we observe that the stabbing circle problem for can be solved in a worst-case optimal $O(n^2)$ time and space by reducing the problem to computing the stabbing planes for a set of segments in 3D.