Collapse process identifies key events in farthest line voronoi diagrams
A Collapse Process for Farthest Voronoi Diagrams of Lines in Three Dimensions
Computational Geometry
Summary
This paper explores how to build a special kind of map, called the farthest Voronoi diagram, for lines in 3D space. The authors describe a step-by-step process, called a collapse process, that changes the map in predictable ways as it looks for the farthest lines. They identify exactly four types of important changes that can happen during the process and explain these changes using 3D geometry. Their work also provides a way to find the smallest sphere touching three lines, which is related to these maps.
What this means in practice
- •For geometric algorithm developers: Implement robust algorithms for farthest Voronoi diagrams of lines in 3D using the complete list of structural change events identified.
- •For computer-aided design teams: Use the method to find smallest spheres tangent to three lines, improving geometric modeling and analysis tools.
Authors
Evanthia Papadopoulou, Martin Suderland, Zeyu Wang
Abstract
We study a \emph{collapse process} to construct the farthest Voronoi diagram of lines in three dimensions, given a spherical map of the diagram's unbounded features. The collapse process sweeps through the diagram in order of decreasing distance from the farthest lines. It follows the \emph{shrinking map}, a cell complex on a topological sphere that encodes the locus of points with a fixed farthest distance. We show that, in three dimensions, the collapse process has exactly four non-terminal local event types that change the structure of the shrinking map: \emph{deletion, swap, local minimum}, and \emph{local maximum} events; plus one terminal event. This list is complete. We give intrinsic three-dimensional geometric descriptions of the four non-terminal events. First, we classify the two vertex-related events, deletion and swap events, by the spherical convex hull of the four tangent points from a vertex to its four defining lines. Then, we analyze the events related to the local extrema of the distance function along the trisector of three lines. We show that the distance function along a trisector has at most $4$ local maxima and $8$ local minima, and that both bounds are tight. The extrema can be found via a polynomial of degree $12$. As a byproduct, this gives a direct method for finding the smallest sphere tangent to three given lines. At each local extremum, the tangent sphere touches the three lines at points lying on a great circle. The collapse process and the completeness of the event list also apply, under similar general position assumptions, to the farthest Voronoi diagram of convex sites under strictly convex distance functions.