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

Math @ Duke





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

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


Publications [#315094] of Pankaj K. Agarwal

Papers Published

  1. Agarwal, PK; Fox, K; Salzman, O, An efficient algorithm for computing high-quality paths amid polygonal obstacles, Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, vol. 2 (January, 2016), pp. 1179-1192, ISBN 9781510819672
    (last updated on 2017/12/10)

    Abstract:
    © Copyright (2016) by SIAM: Society for Industrial and Applied Mathematics. We study a path-planning problem amid a set 0 of obstacles in R2, in which we wish to compute a short path between two points while also maintaining a high clearance from 0; the clearance of a point is its distance from a nearest obstacle in 0. Specifically, the problem asks for a path minimizing the reciprocal of the clearance integrated over the length of the path. We present the first polynomial-time approximation scheme for this problem. Let n be the total number of obstacle vertices and let ϵ ∈ (0, 1]. Our algorithm computes in time 0(n2/ϵ2 log n/ϵ) a path of total cost at most (1 + ϵ) times the cost of the optimal path.

 

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

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