Three dimensional euclidean Voronoi diagrams of lines with a fixed number of orientations
Vladlen Koltun, Micha Sharir · 2002
(MATH) We show that the combinatorial complexity of the Euclidean Voronoi diagram of n lines in $\reals3 that have at most c distinct orientations, is O(c 4 n 2+ε), for any ε>0. This result is a step towards 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.