Document Type

Technical Report

Department

Computer Science and Engineering

Publication Date

1994-01-01

Filename

WUCS-94-31.PDF

Technical Report Number

WUCS-94-31

Abstract

We propose a n extremely simple approximation scheme for computing shortest paths on the surface of a convex polytope in three dimensions. Given a convex polytope P with n vertices and two points p,q on its surface, let dp (p,q) denote the shortest path distance between p and q on the surface of P. Our algorithm produces a path of length at most 2 × dp(p,q) in time O(n). Extending this results, we can also compute ana pproximation of the shortest path tree rooted at an arbitrary point χ Є P in time O(n log n). In the approximate tree, the distance between a vertex ν Є P and χ is at most c × dp(χ, ν), where c = 2.38(1+ε) for any fixed ε > 0. The best algorithm for computing an exact shortest path on a convex polytopt take Ω(n2) time in the worst case; in addition, they are too complicated to be suitable in practice. We can also get a weak approximation result in the general case of k disjoint convex polyhedra: in O(n) time our algorithm gives a path of length at most 2k times the optimal.

Comments

Permanent URL: http://dx.doi.org/10.7936/K7XW4H09

Download

Share

COinS