Constant Storage for Storing Shortest Paths for a Polyhedron

We present a new scheme for storing shortest path information for a polyhedron. This scheme is obtained by applying the constant storage scheme of Han and Saxena [3] on the outward layout of Sharir and Schorr [7]. We achieve constant storage and O(log n+k) time for computing the shortest path from the source point to a query point on the polyhedron, where k is the number of polyhedron edges this shortest path passes through. This improves the result of Chen and Han [2] which uses O(n log n/d) storage and O(d log n/ log d + k) time, where d is an adjustable parameter.

• Algorithms and Theory