Voronoi Diagrams on the Surface of a Polyhedron.

TitleVoronoi Diagrams on the Surface of a Polyhedron.
Publication TypeReports
Year of Publication1985
AuthorsMount D
Date Published1985/05//
InstitutionCENTER FOR AUTOMATION RESEARCH, UNIVERSITY OF MARYLAND COLLEGE PARK
Keywords*POLYGONS, *Polyhedrons, algorithms, DIAGRAMS., EDGES, INTERROGATION, PATHS, PE61102F, POSITION(LOCATION), SURFACES, THEORETICAL MATHEMATICS, WUAFOSR2304A7
Abstract

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)

URLhttp://stinet.dtic.mil/oai/oai?&verb=getRecord&metadataPrefix=html&identifier=ADA166220