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 give n individual trajectory. As the points move, their Voronoi diagram cha nges continuously, but at certain critical instants in time, topologic al events occur that cause a change in the Voronoi diagram. In this pa per, 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 top ological events has an upper bound of O(n(d) lambda(s) (n)), where lam bda(s)(n) is the (nearly linear) maximum length of a (n,s)-Davenport-S chinzel 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 (wh ile 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 topolo gical events.