three dimensional euclidean voronoi diagrams of lines with a fixed number of orientations
(MATH) We show that the combinatorial complexity of the Euclidean Voronoi diagram of n lines in $\reals 3 that have at most c distinct orientations, is O ( c 4 n 2+&egr; ), for any &egr;>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.
three dimensions voronoi diagrams lines lower envelopes