Journal article
Approximating shortest paths on a nonconvex polyhedron
SIAM journal on computing, Vol.30(4), pp.1321-1340
2001
DOI: 10.1137/S0097539799352759
Abstract
We present an approximation algorithm that, given the boundary P of a simple, nonconvex polyhedron in ℝ3 and two points s and t on P, constructs a path on P between s and t whose length is at most 7(1 + ε)dP(s, t), where dP(s, t) is the length of the shortest path between s and t on P, and ε > 0 is an arbitrarily small positive constant. The algorithm runs in O(n5/3 log5/3 n) time, where n is the number of vertices in P. We also present a slightly faster algorithm that runs in O(n8/5 log8/5 n) time and returns a path whose length is at most 15(1 + ε)dP(s, t).
Details
- Title: Subtitle
- Approximating shortest paths on a nonconvex polyhedron
- Creators
- Kasturi R Varadarajan - University of IowaPankaj K Agarwal - Duke University
- Resource Type
- Journal article
- Publication Details
- SIAM journal on computing, Vol.30(4), pp.1321-1340
- Publisher
- Society for Industrial and Applied Mathematics
- DOI
- 10.1137/S0097539799352759
- ISSN
- 0097-5397
- eISSN
- 1095-7111
- Language
- English
- Date published
- 2001
- Academic Unit
- Computer Science
- Record Identifier
- 9984259490902771
Metrics
16 Record Views