Computing shortest paths in the plane with removable obstacles
From MaRDI portal
\(L_1\) shortest pathsEuclidean shortest pathsremovable polygonal obstaclesstochastic shortest paths
Data structures (68P05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)
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
Cites work
- k-violation linear programming
- A nearly optimal algorithm for finding \(L _{1}\) shortest paths among polygonal obstacles in the plane
- A new algorithm for computing visibility graphs of polygonal obstacles in the plane
- Algorithms and Computation
- An Optimal Algorithm for Euclidean Shortest Paths in the Plane
- Bicriteria rectilinear shortest paths among rectilinear obstacles in the plane
- Computing shortest paths amid convex pseudodisks
- Computing shortest paths among curved obstacles in the plane
- Computing shortest paths with uncertainty
- scientific article; zbMATH DE number 1424303 (Why is no real title available?)
- Low-Dimensional Linear Programming with Violations
- ON BENDS AND LENGTHS OF RECTILINEAR PATHS: A GRAPH-THEORETIC APPROACH
- On geometric optimization with few violated constraints
- ON GEOMETRIC PATH QUERY PROBLEMS
- Planar rectilinear shortest path computation using corridors
- Rectilinear Path Problems among Rectilinear Obstacles Revisited
- Rectilinear paths among rectilinear obstacles
- Shortest path problem with uncertain arc lengths
- Shortest Path Queries Among Weighted Obstacles in the Rectilinear Plane
- Shortest paths in the plane with obstacle violations
- SHORTEST RECTILINEAR PATHS AMONG WEIGHTED OBSTACLE
- Stochastic minimum spanning trees in Euclidean spaces
- The weighted region problem
- Visibility Algorithms in the Plane
Cited in
(8)- Shortest paths among transient obstacles
- Shortest paths in the plane with obstacle violations
- Improved approximation bounds for the minimum constraint removal problem
- SHORTEST PATH AMIDST DISC OBSTACLES IS COMPUTABLE
- Improved approximation bounds for the minimum constraint removal problem
- Approximate Shortest Paths in Polygons with Violations
- SHORTEST PATHS AMONG OBSTACLES IN THE PLANE
- Removing Connected Obstacles in the Plane is FPT
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)
