Approximating Shortest Paths on a Nonconvex Polyhedron
Kasturi Varadarajan, Pankaj K. Agarwal · SIAM Journal on Computing · 2000
We present an approximation algorithm that, given the boundary P of a simple, nonconvex polyhedron in ${\mathbb R}^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+{\varepsilon})} d P (s,t), where d P (s,t) is the length of the shortest path between s and t on P, and ${\varepsilon} > 0$ is an arbitrarily small positive constant. The algorithm runs in O(n 5/3 log 5/3 n ) time, where n is the number of vertices in P. We also present a slightly faster algorithm that runs in O(n 8/5 log 8/5 n ) time and returns a path whose length is at most ${15(1+{\varepsilon})} d_{P}(s,t)$.