# Computing shortest paths in the plane with removable obstacles

Conference Paper

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