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 Atallah?
 Status/Conjectures
 Open.
Conjectured to be nearly quadratic.
 Partial and Related Results
 The best lower bound known is quadratic, and the best
upper bound is cubic [SA95, p. 297].
If the speeds are allowed to differ, the upper bound
remains essentially cubic [AGMR98].
The general belief is that the complexity should be
close to quadratic; Chew [Che97] showed this to be the case
if the underlying metric is L_{1} (or L_{∞}).
 Appearances
 [MO01]
 Categories
 Voronoi diagrams; Delaunay triangulations
 Entry Revision History
 J. O'Rourke, 1 Aug. 2001.
 AGMR98

G. Albers, Leonidas J. Guibas, Joseph S. B. Mitchell, and T. Roos.
Voronoi diagrams of moving points.
Internat. J. Comput. Geom. Appl., 8:365380, 1998.
 Che97

L. P. Chew.
Nearquadratic bounds for the L_{1} Voronoi diagram of moving
points.
Comput. Geom. Theory Appl., 7:7380, 1997.
 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.
 SA95

Micha Sharir and P. K. Agarwal.
DavenportSchinzel Sequences and Their Geometric
Applications.
Cambridge University Press, New York, 1995.
The Open Problems Project  December 04, 2015