← All problems

Voronoi Diagram of Lines in 3D

Let nNn\in\mathbb{N} be the number of input objects, where the input consists either of nn lines or of nn line segments in three-dimensional Euclidean space. Determine the combinatorial complexity of the resulting Voronoi diagram as a function of nn. In particular, close the gap between the known lower bound of Ω(n2)\Omega(n^2) and the essentially cubic upper bound, and decide whether the conjectured nearly quadratic complexity holds.

Organizer

Boyuan Wang portraitBoyuan Wang
Minghan Wang portraitMinghan Wang
Bochao Li portraitBochao Li