Planar rectilinear shortest path computation using corridors
From MaRDI portal
The authors study the problem of finding a 2-dimensional rectilinear (\(L_1\)) shortest path between two points in a polygonal region comprising non-intersecting polygonal obstacles. They propose an algorithm that builds a restricted visibility graph and then applies Dijkstra's shortest path algorithm on this visibility graph [cf. \textit{J. Hershberger} and \textit{S. Suri}, SIAM J. Comput. 28, No.~6, 2215--2256 (1999; Zbl 0939.68157)]. A shorter version of the paper appeared in [Lecture Notes in Computer Science 4855, 412--423 (2007; Zbl 1135.68600)].
Recommendations
- Finding a Rectilinear Shortest Path in R 2 Using Corridor Based Staircase Structures
- Rectilinear Path Problems among Rectilinear Obstacles Revisited
- A nearly optimal algorithm for finding \(L _{1}\) shortest paths among polygonal obstacles in the plane
- SHORTEST RECTILINEAR PATHS AMONG WEIGHTED OBSTACLE
- Minimum-link shortest paths for polygons amidst rectilinear obstacles
Cites work
- \(L_ 1\) shortest paths among polygonal obstacles in the plane
- Algorithms for Reporting and Counting Geometric Intersections
- An efficient algorithm for Euclidean shortest paths among polygonal obstacles in the plane
- An Optimal Algorithm for Euclidean Shortest Paths in the Plane
- An Output-Sensitive Algorithm for Computing Visibility Graphs
- Constructing the visibility graph for n-line segments in \(O(n^ 2)\) time
- Efficient approximate shortest-path queries among isothetic rectangular obstacles
- Efficiently Constructing the Visibility Graph of a Simple Polygon with Obstacles
- Finding a Rectilinear Shortest Path in R 2 Using Corridor Based Staircase Structures
- On parallel rectilinear obstacle-avoiding paths
- On Vertical Visibility in Arrangements of Segments and the Queue Size in the Bentley-Ottmann Line Sweeping Algorithm
- ORTHOGONAL SHORTEST ROUTE QUERIES AMONG AXES PARALLEL RECTANGULAR OBSTACLES
- Planar spanners and approximate shortest path queries among obstacles in the plane
- Rectilinear short path queries among rectangular obstacles
- Rectilinear shortest paths in the presence of rectangular barriers
- TRIANGULATING DISJOINT JORDAN CHAINS
Cited in
(21)- Finding a region with the minimum total L₁ distance from prescribed terminals
- Characterizing the shortest path of an object among obstacles
- Computing an \(L_1\) shortest path among splinegonal obstacles in the plane
- Routing among convex polygonal obstacles in the plane
- Visibility and ray shooting queries in polygonal domains
- Computing a rectilinear shortest path amid splinegons in plane
- Computing \(L_1\) shortest paths among polygonal obstacles in the plane
- An algorithm for finding shortest paths in a maze
- scientific article; zbMATH DE number 30300 (Why is no real title available?)
- On finding a shortest isothetic path and its monotonicity inside a digital object
- A divide-and-conquer algorithm for two-point L₁ shortest path queries in polygonal domains
- Computing shortest paths in the plane with removable obstacles
- Computing the visibility polygon of an island in a polygonal domain
- Computing the \(L_1\) geodesic diameter and center of a polygonal domain
- Finding a Rectilinear Shortest Path in R 2 Using Corridor Based Staircase Structures
- An efficient direct approach for computing shortest rectilinear paths among obstacles in a two-layer interconnection model
- Path planning in a weighted planar subdivision under the Manhattan metric
- Finding a shortest pair of paths on the plane with obstacles and crossing areas
- Routing among convex polygonal obstacles in the plane
- Routing among convex polygonal obstacles in the plane using a simplified domain
- Computing skeletons for rectilinearly convex obstacles in the rectilinear plane
This page was built for publication: Planar rectilinear shortest path computation using corridors
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q833714)
