# Approximating shortest paths on a nonconvex polyhedron

Published

Journal Article

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). © 2000 Society for Industrial and Applied Mathematics.

### Full Text

### Duke Authors

### Cited Authors

- Varadarajan, KR; Agarwal, PK

### Published Date

- January 1, 2000

### Published In

### Volume / Issue

- 30 / 4

### Start / End Page

- 1321 - 1340

### International Standard Serial Number (ISSN)

- 0097-5397

### Digital Object Identifier (DOI)

- 10.1137/S0097539799352759

### Citation Source

- Scopus