next up previous
Next: Problem 3: Voronoi Diagram Up: The Open Problems Project Previous: Problem 1: Minimum Weight

Problem 2: Voronoi Diagram of Moving Points

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?
Unknown (to JOR). Perhaps Michael Atallah?
Long conjectured to be nearly quadratic. Solved now: [Rub15]. Natan Rubin proved an upper bound of O(n2+ε), and a quadratic lower bound is known.
Partial and Related Results
See [Rub15] for a review of earlier work, now superceded.
Voronoi diagrams; Delaunay triangulations
Entry Revision History
J. O'Rourke, 1 Aug. 2001; 19Sep2017.


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.

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

The Open Problems Project - September 19, 2017