Constant storage for computing shortest paths for a polyhedron
No Thumbnail Available
Authors
Meeting name
Sponsors
Date
Journal Title
Format
Subject
Abstract
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 [5] on the outward layout of Sharir and Schorr [10]. 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/ log d) storage and O(d log n/ log d + k) time, where d is an adjustable parameter.
Table of Contents
Introduction -- Inward and outward layouts -- Storing shortest path information in constant storage for computing shortest paths -- Main theorem -- Conclusions
DOI
PubMed ID
Degree
M.S. (Master of Science)