Voronoi diagrams for parallel halflines in 3D

F. Aurenhammer, G. Paulini, and B. Jüttler


We consider the Euclidean Voronoi diagram for a set of $n$ parallel halflines in 3-space. A relation of this diagram to planar power diagrams is shown, and is used to analyze its geometric and topological properties. Moreover, a simple plane-sweep algorithm is given that computes the Voronoi diagram for parallel halflines at logarithmic cost per face.

Reference: F. Aurenhammer, G. Paulini, and B. Jüttler. Voronoi diagrams for parallel halflines in 3D. In Proc. $32^{nd}$ European Workshop on Computational Geometry EuroCG '2016, pages 127-130, Lugano, Switzerland, 2016.