Agarwal, Pankaj K. ;
Kumar, Neeraj ;
Sintos, Stavros ;
Suri, Subhash
Computing Shortest Paths in the Plane with Removable Obstacles
Abstract
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 c_i > 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 + epsilon)approximate shortest path in time O({nh}/{epsilon^2} log n log n/epsilon) with removal cost at most (1+epsilon)C, where h is the number of obstacles, n is the total number of obstacle vertices, and epsilon in (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 st path queries in polylogarithmic time, for any pair of points s, t in the plane.
BibTeX  Entry
@InProceedings{agarwal_et_al:LIPIcs:2018:8831,
author = {Pankaj K. Agarwal and Neeraj Kumar and Stavros Sintos and Subhash Suri},
title = {{Computing Shortest Paths in the Plane with Removable Obstacles}},
booktitle = {16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)},
pages = {5:15:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770682},
ISSN = {18688969},
year = {2018},
volume = {101},
editor = {David Eppstein},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8831},
URN = {urn:nbn:de:0030drops88312},
doi = {10.4230/LIPIcs.SWAT.2018.5},
annote = {Keywords: Euclidean shortest paths, Removable polygonal obstacles, Stochastic shortest paths, L_1 shortest paths}
}
2018
Keywords: 

Euclidean shortest paths, Removable polygonal obstacles, Stochastic shortest paths, L_1 shortest paths 
Seminar: 

16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)

Issue date: 

2018 
Date of publication: 

2018 