VORONOI DIAGRAMS OF MOVING POINTS IN THE PLANE
- 1 March 1991
- journal article
- Published by World Scientific Pub Co Pte Ltd in International Journal of Computational Geometry & Applications
- Vol. 1 (1) , 23-32
- https://doi.org/10.1142/s0218195991000037
Abstract
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(k2n3 log n · 2O(α(n)5k+1)) time to process moving functions of given points, and uses O(k2n32O(α(n)5k+1)) space to store the preprocessing result where α(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(n) time which is optimal.Keywords
This publication has 0 references indexed in Scilit: