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₁ (or L_$\infty$).

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 L₁ 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.