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 Atallah?
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 L1 (or L).
Voronoi diagrams; Delaunay triangulations
Entry Revision History
J. O'Rourke, 1 Aug. 2001.


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

L. P. Chew.
Near-quadratic bounds for the L1 Voronoi diagram of moving points.
Comput. Geom. Theory Appl., 7:73-80, 1997.

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.

Micha Sharir and P. K. Agarwal.
Davenport-Schinzel Sequences and Their Geometric Applications.
Cambridge University Press, New York, 1995.

The Open Problems Project - December 04, 2015