Accession Number : ADA166246


Title :   On Finding Shortest Paths on Convex Polyhedra.


Descriptive Note : Technical rept.,


Corporate Author : MARYLAND UNIV COLLEGE PARK CENTER FOR AUTOMATION RESEARCH


Personal Author(s) : Mount,David M


Full Text : https://apps.dtic.mil/dtic/tr/fulltext/u2/a166246.pdf


Report Date : May 1985


Pagination or Media Count : 35


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'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)


Descriptors :   *ALGORITHMS , *PREPROCESSING , *POLYGONS , OUTPUT , POSITION(LOCATION) , ROBOTICS , PATHS , MOTION , TIME , PLANNING , BARRIERS , AUTONOMOUS NAVIGATION , INTERROGATION , AVOIDANCE


Subject Categories : Theoretical Mathematics


Distribution Statement : APPROVED FOR PUBLIC RELEASE