Computing shortest paths in the plane with removable obstacles
© 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.
Agarwal, PK; Kumar, N; Sintos, S; Suri, S
Volume / Issue
Start / End Page
International Standard Serial Number (ISSN)
International Standard Book Number 13 (ISBN-13)
Digital Object Identifier (DOI)