Title: VORONOI DIAGRAMS OF MOVING POINTS IN THE PLANE
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(k 2 n 3 log n · 2 O(α(n) 5k+1 ) ) time to process moving functions of given points, and uses O(k 2 n 3 2 O(α(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.
Publication Year: 1991
Publication Date: 1991-03-01
Language: en
Type: article
Indexed In: ['crossref']
Access and Citation
Cited By Count: 61
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot