Voronoi diagrams of moving points

Consider a set of n points in d-dimensional Euclidean space, d ≥ 2, each of which is continuously moving along a given individual trajectory. As the points move, their Voronoi diagram changes continuously, but at certain critical instants in time, topological events occur that cause a change in the Voronoi diagram. In this paper, we present a method of maintaining the Voronoi diagram over time, at a cost of O(log n) per event, while showing that the number of topological events has an upper bound of O(n^dΛ,(n)), where Λ,(n) is the nearly linear) maximum length of a (n, s)-DavenportSchinzel sequence, and s is a constant depending on the motions of the point sites. In addition, we show that if only k points are moving (while leaving the other n - k points fixed), there is an upper bound of O(kn^d-1Λ,(n) + (n -k)^dΛ,(k)) on the number of topological events.