The Open Problems Project

Next: Problem 3: Voronoi Diagram of Lines in 3D

Previous: Problem 1: Minimum Weight Triangulation

Problem 2: Voronoi Diagram of Moving Points

Statement

What is the maximum number of combinatorial changes possible in a Euclidean Voronoi diagram of a set of n points each moving along a line at unit speed in two dimensions?

Origin

Unknown (to JOR). Perhaps Michael Atallah?

Status/Conjectures

Long conjectured to be nearly quadratic. Solved now: [Rub15]. Natan Rubin proved an upper bound of O(n^{2+\epsilon}), and a quadratic lower bound is known.

Partial and Related Results

See [Rub15] for a review of earlier work, now superceded.

Appearances

[MO01]

Categories

Voronoi diagrams; Delaunay triangulations

Entry Revision History

J. O’Rourke, 1 Aug. 2001; 19Sep2017.

Bibliography

[MO01]

J. S. B. Mitchell and Joseph O’Rourke. Computational geometry column 42. Internat. J. Comput. Geom. Appl., 11(5):573–582, 2001. Also in SIGACT News 32(3):63-72 (2001), Issue 120.

[Rub15]

Natan Rubin. On kinetic Delaunay triangulations: A near-quadratic bound for unit speed motions. Journal of the ACM, 62(3):25, 2015.