@article {15671,
	title = {On Finding Shortest Paths on Convex Polyhedra.},
	year = {1985},
	month = {1985/05//},
	institution = {CENTER FOR AUTOMATION RESEARCH, UNIVERSITY OF MARYLAND COLLEGE PARK},
	abstract = {Applications in robotics and autonomous navigation have motivated the study of motion planning and obstacle avoidance algorithms. The special case considered here is that of moving a point (the object) along the surface of a convex polyhedron (the obstacle) with n vertices. Sharir and Schorr have developed an algorithm that, given a source point on the surface of a convex polyhedron, determines the shortest path from the source to any point on the polyhedron in linear time after O(n cubed log n) preprocessing time. The preprocessed output requires O(n squared) space. By using known algorithms for fast planar point location, the shortest path query time for Sharir and Schorr{\textquoteright}s algorithm is shown to be O(k + log n) where k is the number faces traversed by the path. We give an improved preprocessing algorithm that runs in O(n squared log n) time requiring the same query time and space. We also show how to store the output of the preprocessing algorithm in O(n log n) space while maintaining the same query time. (Author)},
	keywords = {*ALGORITHMS, *POLYGONS, *Polyhedrons, *PREPROCESSING, AUTONOMOUS NAVIGATION, AVOIDANCE., BARRIERS, INTERROGATION, MOTION, output, PATHS, PE61102F, planning, POSITION(LOCATION), ROBOTICS, THEORETICAL MATHEMATICS, TIME},
	url = {http://stinet.dtic.mil/oai/oai?\&verb=getRecord\&metadataPrefix=html\&identifier=ADA166246},
	author = {Mount, Dave}
}
@article {15672,
	title = {Voronoi Diagrams on the Surface of a Polyhedron.},
	year = {1985},
	month = {1985/05//},
	institution = {CENTER FOR AUTOMATION RESEARCH, UNIVERSITY OF MARYLAND COLLEGE PARK},
	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{\textquoteright}s surface. (Author)},
	keywords = {*POLYGONS, *Polyhedrons, algorithms, DIAGRAMS., EDGES, INTERROGATION, PATHS, PE61102F, POSITION(LOCATION), SURFACES, THEORETICAL MATHEMATICS, WUAFOSR2304A7},
	url = {http://stinet.dtic.mil/oai/oai?\&verb=getRecord\&metadataPrefix=html\&identifier=ADA166220},
	author = {Mount, Dave}
}
