VORONOI DIAGRAMS OF MOVING POINTS IN THE PLANE

In this paper, we consider the dynamic Voronoi diagram problem. In this problem, a given set of planar points are moving and our objective is to find the Voronoi diagram of these moving points at any time t. A preprocessing algorithm and a query processing algorithm are presented in this paper. Assume that the points are in k-motion, and it takes O(k) time to find roots of a polynomial with degree O(k). The preprocessing algorithm takes O(k(2)n(3) log n.2(O(alpha(n)5k+l))) time to process moving functions of given points, and uses O(k(2)n(3)2(O(alpha(n)5k+1))) space to store the preprocessing result where alpha(n) is the functional inverse of Ackermann's function. The query processing algorithm is designed to report the Voronoi diagram of these points for a query time t. It takes O(a) time which is optimal.