Math @ Duke

Publications [#235591] of Pankaj K. Agarwal
Papers Published
 Varadarajan, KR; Agarwal, PK, Approximating shortest paths on a nonconvex polyhedron,
Annual Symposium on Foundations of Computer Science  Proceedings
(1997),
pp. 182191
(last updated on 2017/12/13)
Abstract: We present an approximation algorithm that, given the boundary P of a simple, nonconvex polyhedron in R3, 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).


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

