Near-quadratic bounds for the L1 Voronoi diagram of moving points
L. Paul Chew · Computational Geometry · 1997
Given a set of n moving points in the plane, how many topological changes occur in the Voronoi diagram of the points? If each point has constant velocity then there is an upper bound of O(n3) (Guibas et al., 1991) and an easy lower bound of Ω(n2). It is widely believed that the true upper bound should be close to O(n2). We show this belief to be true for the case of Voronoi diagrams based on the L1 (or L∞) metric; the number of changes is shown to be O(n2α(n)) where α(n) grows so slowly it is effectively a small constant for all reasonable values of n.