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

Math @ Duke



Publications [#336324] of Pankaj K. Agarwal

Papers Published

  1. 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. 51-515, ISBN 9783959770682 [doi]
    (last updated on 2019/04/21)

    © 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 pairwise-disjoint 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 NP-hard even if the obstacles are vertical line segments. Our main result is a fully-polynomial time approximation scheme (FPTAS) for the case of convex polygons. Specifically, we compute an (1 + )-approximate shortest path in time Onh2 log n logn with 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 user-specified 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.
ph: 919.660.2800
fax: 919.660.2821

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