Department of Mathematics
 Search | Help | Login | pdf version | printable version

Math @ Duke





.......................

.......................


Publications [#235427] of Pankaj K. Agarwal

Papers Published

  1. Varadarajan, KR; Agarwal, PK, Approximating shortest paths on a nonconvex polyhedron, SIAM Journal on Computing, vol. 30 no. 4 (2000), pp. 1321-1340, ISSN 0097-5397
    (last updated on 2017/12/11)

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

 

dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821

Mathematics Department
Duke University, Box 90320
Durham, NC 27708-0320