Math @ Duke

Publications [#315094] of Pankaj K. Agarwal
Papers Published
 Agarwal, PK; Fox, K; Salzman, O, An efficient algorithm for computing highquality paths amid polygonal obstacles,
Proceedings of the Annual ACMSIAM Symposium on Discrete Algorithms, vol. 2
(January, 2016),
pp. 11791192, ISBN 9781510819672
(last updated on 2017/12/13)
Abstract: © Copyright (2016) by SIAM: Society for Industrial and Applied Mathematics. We study a pathplanning 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 polynomialtime 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 277080320

