Math @ Duke

Publications [#337580] of Pankaj K. Agarwal
Papers Published
 Agarwal, PK; Kyle, FOX; Salzman, O, An efficient algorithm for computing highquality paths amid polygonal obstacles,
Acm Transactions on Algorithms, vol. 14 no. 4
(August, 2018),
pp. 121, Association for Computing Machinery (ACM) [doi]
(last updated on 2019/04/24)
Abstract: © 2018 ACM. We study a pathplanning problem amid a set O of obstacles in R2, in which we wish to compute a short path between two points while also maintaining a high clearance from O; the clearance of a point is its distance from a nearest obstacle in O. 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 O(nε22 lognε ) 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

