Computing Shortest Paths in the Plane with Removable Obstacles

DOI10.4230/LIPIcs.SWAT.2018.5zbMath1477.68454OpenAlexW2810759650MaRDI QIDQ5116468

Stavros Sintos, Neeraj Kumar, Pankaj K. Agarwal, Subhash Suri

Publication date: 25 August 2020

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2018/8831/pdf/LIPIcs-SWAT-2018-5.pdf/

zbMATH Keywords

stochastic shortest pathsEuclidean shortest paths\(L_1\) shortest pathsremovable polygonal obstacles

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Data structures (68P05) Approximation algorithms (68W25)

Related Items

Shortest paths among transient obstacles, Shortest paths in the plane with obstacle violations, Unnamed Item, Improved approximation bounds for the minimum constraint removal problem, Approximate Shortest Paths in Polygons with Violations

Cites Work

• Unnamed Item
• Unnamed Item
• Shortest path problem with uncertain arc lengths
• Planar rectilinear shortest path computation using corridors
• \(k\)-violation linear programming
• On geometric optimization with few violated constraints
• Rectilinear paths among rectilinear obstacles
• Computing Shortest Paths amid Convex Pseudodisks
• A new algorithm for computing visibility graphs of polygonal obstacles in the plane
• A Nearly Optimal Algorithm for Finding L 1 Shortest Paths among Polygonal Obstacles in the Plane
• Computing shortest paths with uncertainty
• SHORTEST RECTILINEAR PATHS AMONG WEIGHTED OBSTACLE
• ON BENDS AND LENGTHS OF RECTILINEAR PATHS: A GRAPH-THEORETIC APPROACH
• An Optimal Algorithm for Euclidean Shortest Paths in the Plane
• The weighted region problem
• Bicriteria Rectilinear Shortest Paths among Rectilinear Obstacles in the Plane
• ON GEOMETRIC PATH QUERY PROBLEMS
• Rectilinear Path Problems among Rectilinear Obstacles Revisited
• Shortest Path Queries Among Weighted Obstacles in the Rectilinear Plane
• Computing Shortest Paths among Curved Obstacles in the Plane
• Low-Dimensional Linear Programming with Violations
• Stochastic minimum spanning trees in euclidean spaces
• Visibility Algorithms in the Plane
• Algorithms and Computation