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?
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
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
Cambridge University Press, New York, 1995.
The Open Problems Project - December 08, 2012