Point location in Voronoi diagrams of polygons

摘要

Given a query point and the Voronoi diagram of a polygon (VD(P)), how to efficiently find the Voronoi region (VR) containing the query point, i.e., the point location in VD(P), is a fundamental operation for many other algorithms based on VD(P), such as path planning, visibility, and so on. A triangulation refinement method for VD(P) is presented in this paper, and then a point-location data structure is provided so that the VR containing the query point can be reported in O(logn) time. The algorithm takes O(n) space and O(nlogn) preprocessing time.