Next: Problem 3: Voronoi Diagram
Up: The Open Problems Project
Previous: Problem 1: Minimum Weight
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+ε}),
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.
 MO01

J. S. B. Mitchell and Joseph O'Rourke.
Computational geometry column 42.
Internat. J. Comput. Geom. Appl., 11(5):573582, 2001.
Also in SIGACT News 32(3):6372 (2001), Issue 120.
 Rub15

Natan Rubin.
On kinetic Delaunay triangulations: A nearquadratic bound for unit
speed motions.
Journal of the ACM (JACM), 62(3):25, 2015.
The Open Problems Project  September 19, 2017