3-Dimensional Euclidean Voronoi Diagrams of Lines with a Fixed Number of Orientations
Vladlen Koltun, Micha Sharir · SIAM Journal on Computing · 2003
We show that the combinatorial complexity of the Euclidean Voronoi diagram of n lines in $\mathbb{R}^3$ that have at most c distinct orientations is $O(c^3n^{2+\varepsilon})$ for any $\varepsilon>0$. This result is a step toward proving the long-standing conjecture that the Euclidean Voronoi diagram of lines in three dimensions has near-quadratic complexity. It provides the first natural instance in which this conjecture is shown to hold. In a broader context, our result adds a natural instance to the (rather small) pool of instances of general 3-dimensional Voronoi diagrams for which near-quadratic complexity bounds are known.