On Finding Shortest Paths on Convex Polyhedra.

摘要

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)