Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH scholarly article en Agarwal, Pankaj K.; Kumar, Neeraj; Sintos, Stavros; Suri, Subhash http://www.dagstuhl.de/lipics License
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-88312
URL:

; ; ;

Computing Shortest Paths in the Plane with Removable Obstacles

pdf-format:


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 pairwise-disjoint 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 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 + 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 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.

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:1--5:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-068-2},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{101},
  editor =	{David Eppstein},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/8831},
  URN =		{urn:nbn:de:0030-drops-88312},
  doi =		{10.4230/LIPIcs.SWAT.2018.5},
  annote =	{Keywords: Euclidean shortest paths, Removable polygonal obstacles, Stochastic shortest paths, L_1 shortest paths}
}

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


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI