Computing Shortest Paths in the Plane with Removable Obstacles

DOI10.4230/LIPIcs.SWAT.2018.5zbMath1477.68454MaRDI 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 paths; Euclidean shortest paths; \(L_1\) shortest paths; removable polygonal obstacles

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68U05: Computer graphics; computational geometry (digital and algorithmic aspects)

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

68P05: Data structures

68W25: Approximation algorithms

Related Items

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

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