Voronoi Diagrams on the Surface of a Polyhedron

摘要

This document presents an algorithm that computes the Voronol diagram of a set of point lying on the surface of a possibly nonconvex polyhedron. Distances are measured in the Euclidean metric along the surface of the polyhedron. The algorithm runs in O(n squared log n) time and requires O(n squared) space to store the final data structure, where n is the maximum of the number of edges and source points on the polyhedron. This algorithm generalizes or improves the running times of a number of shortest path problems both on polyhedra and in the plane amidst polygonal obstacles. By applying standard algorithms for point location, we can determine the distance from a query point to the nearest source in O(log n) time and can list the shortest path in O(k + log n) time, where k is the number of faces traversed by the path. The algorithm achieves its efficiency by a novel method of searching the polyhedron's surface. (Author)