← All problems
Voronoi Diagram of Lines in 3D
Let be the number of input objects, where the input consists either of lines or of line segments in three-dimensional Euclidean space. Determine the combinatorial complexity of the resulting Voronoi diagram as a function of . In particular, close the gap between the known lower bound of and the essentially cubic upper bound, and decide whether the conjectured nearly quadratic complexity holds.
