TY - RPRT T1 - On Finding Shortest Paths on Convex Polyhedra. Y1 - 1985 A1 - Mount, Dave KW - *ALGORITHMS KW - *POLYGONS KW - *Polyhedrons KW - *PREPROCESSING KW - AUTONOMOUS NAVIGATION KW - AVOIDANCE. KW - BARRIERS KW - INTERROGATION KW - MOTION KW - output KW - PATHS KW - PE61102F KW - planning KW - POSITION(LOCATION) KW - ROBOTICS KW - THEORETICAL MATHEMATICS KW - TIME AB - 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'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) PB - CENTER FOR AUTOMATION RESEARCH, UNIVERSITY OF MARYLAND COLLEGE PARK UR - http://stinet.dtic.mil/oai/oai?&verb=getRecord&metadataPrefix=html&identifier=ADA166246 ER -