2026-07-25T14:07:06Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7841 2024-03-06T10:41:21Z ddc:004 open_access

Shortest Paths in the Plane with Obstacle Violations Hershberger, John Kumar, Neeraj Suri, Subhash Shortest paths Polygonal obstacles Continuous Dijkstra Obstacle crossing Visibility We study the problem of finding shortest paths in the plane among h convex obstacles, where the path is allowed to pass through (violate) up to k obstacles, for k <= h. Equivalently, the problem is to find shortest paths that become obstacle-free if k obstacles are removed from the input. Given a fixed source point s, we show how to construct a map, called a shortest k-path map, so that all destinations in the same region of the map have the same combinatorial shortest path passing through at most k obstacles. We prove a tight bound of Theta(kn) on the size of this map, and show that it can be computed in O(k^2 n log n) time, where n is the total number of obstacle vertices. Schloss Dagstuhl – Leibniz-Zentrum für Informatik John Hershberger and Neeraj Kumar and Subhash Suri 2017 Is Part Of LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2017.49 urn:nbn:de:0030-drops-78413 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.49 eng https://creativecommons.org/licenses/by/3.0/legalcode