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 [4] on the outward layout of Sharir and Schorr [8]. 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 [3] which uses O(n log n/d) storage and O(d log n/ log d + k) time, where d is an adjustable parameter.
No takes yet. Share an insight, caveat, or question.
Chen et al. (2024) studied this question.