2026-07-28T19:12:38Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8831 2024-03-06T10:42:45Z ddc:004 open_access

Computing Shortest Paths in the Plane with Removable Obstacles Agarwal, Pankaj K. Kumar, Neeraj Sintos, Stavros Suri, Subhash Euclidean shortest paths Removable polygonal obstacles Stochastic shortest paths L_1 shortest paths 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Pankaj K. Agarwal and Neeraj Kumar and Stavros Sintos and Subhash Suri 2018 Is Part Of LIPIcs, Volume 101, 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SWAT.2018.5 urn:nbn:de:0030-drops-88312 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2018.5 eng https://creativecommons.org/licenses/by/3.0/legalcode