Computing shortest paths in the plane with removable obstacles
DOI10.4230/LIPICS.SWAT.2018.5zbMATH Open1477.68454OpenAlexW2810759650MaRDI QIDQ5116468FDOQ5116468
Pankaj K. Agarwal, Subhash Suri, Stavros Sintos, Neeraj Kumar
Publication date: 25 August 2020
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2018/8831/pdf/LIPIcs-SWAT-2018-5.pdf/
Recommendations
- Shortest paths in the plane with convex polygonal obstacles
- Shortest paths in the plane with polygonal obstacles
- A nearly optimal algorithm for finding \(L _{1}\) shortest paths among polygonal obstacles in the plane
- SHORTEST PATHS AMONG OBSTACLES IN THE PLANE
- Shortest paths in the plane with obstacle violations
stochastic shortest pathsEuclidean shortest paths\(L_1\) shortest pathsremovable polygonal obstacles
Analysis of algorithms and problem complexity (68Q25) Data structures (68P05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)
Cites Work
- Rectilinear paths among rectilinear obstacles
- ON BENDS AND LENGTHS OF RECTILINEAR PATHS: A GRAPH-THEORETIC APPROACH
- Title not available (Why is that?)
- On geometric optimization with few violated constraints
- An Optimal Algorithm for Euclidean Shortest Paths in the Plane
- Visibility Algorithms in the Plane
- Shortest path problem with uncertain arc lengths
- The weighted region problem
- Stochastic minimum spanning trees in euclidean spaces
- \(k\)-violation linear programming
- Low-Dimensional Linear Programming with Violations
- Planar rectilinear shortest path computation using corridors
- A Nearly Optimal Algorithm for Finding L 1 Shortest Paths among Polygonal Obstacles in the Plane
- ON GEOMETRIC PATH QUERY PROBLEMS
- Computing shortest paths with uncertainty
- SHORTEST RECTILINEAR PATHS AMONG WEIGHTED OBSTACLE
- Rectilinear Path Problems among Rectilinear Obstacles Revisited
- Shortest Path Queries Among Weighted Obstacles in the Rectilinear Plane
- Algorithms and Computation
- A new algorithm for computing visibility graphs of polygonal obstacles in the plane
- Computing shortest paths amid convex pseudodisks
- Computing Shortest Paths among Curved Obstacles in the Plane
- Title not available (Why is that?)
- Bicriteria Rectilinear Shortest Paths among Rectilinear Obstacles in the Plane
Cited In (8)
- SHORTEST PATH AMIDST DISC OBSTACLES IS COMPUTABLE
- Shortest paths among transient obstacles
- Approximate Shortest Paths in Polygons with Violations
- SHORTEST PATHS AMONG OBSTACLES IN THE PLANE
- Removing Connected Obstacles in the Plane is FPT
- Shortest paths in the plane with obstacle violations
- Title not available (Why is that?)
- Improved approximation bounds for the minimum constraint removal problem
This page was built for publication: Computing shortest paths in the plane with removable obstacles
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5116468)
