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

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

Bibliography

AGMR98
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.

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

MO01
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.

SA95
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