Computing shortest paths in the plane with removable obstacles

Published

Conference Paper

© 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.

Full Text

Duke Authors

Cited Authors

  • Agarwal, PK; Kumar, N; Sintos, S; Suri, S

Published Date

  • June 1, 2018

Published In

Volume / Issue

  • 101 /

Start / End Page

  • 51 - 515

International Standard Serial Number (ISSN)

  • 1868-8969

International Standard Book Number 13 (ISBN-13)

  • 9783959770682

Digital Object Identifier (DOI)

  • 10.4230/LIPIcs.SWAT.2018.5

Citation Source

  • Scopus