Math @ Duke

Publications [#336324] of Pankaj K. Agarwal
Papers Published
 Agarwal, PK; Kumar, N; Sintos, S; Suri, S, Computing shortest paths in the plane with removable obstacles,
Leibniz International Proceedings in Informatics, Lipics, vol. 101
(June, 2018),
pp. 51515, ISBN 9783959770682 [doi]
(last updated on 2019/02/22)
Abstract: © Pankaj Agarwal, Neeraj Kumar, Stavros Sintos, and Subhash Suri. We consider the problem of computing a Euclidean shortest path in the presence of removable obstacles in the plane. In particular, we have a collection of pairwisedisjoint polygonal obstacles, each of which may be removed at some cost ci> 0. Given a cost budget C > 0, and a pair of points s, t, which obstacles should be removed to minimize the path length from s to t in the remaining workspace? We show that this problem is NPhard even if the obstacles are vertical line segments. Our main result is a fullypolynomial time approximation scheme (FPTAS) for the case of convex polygons. Specifically, we compute an (1 + )approximate shortest path in time Onh2log n lognwith removal cost at most (1 + )C, where h is the number of obstacles, n is the total number of obstacle vertices, and ∈ (0, 1) is a userspecified parameter. Our approximation scheme also solves a shortest path problem for a stochastic model of obstacles, where each obstacle’s presence is an independent event with a known probability. Finally, we also present a data structure that can answer s–t path queries in polylogarithmic time, for any pair of points s, t in the plane.


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

