Voronoi diagrams of moving points

Consider a set of n points in d-dimensional Euclidean space, d greater than or equal to 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) lambda(s) (n)), where lambda(s)(n) is the (nearly linear) maximum length of a (n,s)-Davenport-Schinzel 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)lambda(s) (n) + (n-k)(d) lambda(s) (k)) on the number of topological events.