Finding a Rectilinear Shortest Path in R 2 Using Corridor Based Staircase Structures

DOI10.1007/978-3-540-77050-3_34MaRDI QIDQ5458853zbMATH OpenOpenAlexFDO

Authors Rajasekhar Inkulu, Sanjiv Kapoor

Publication date 24 April 2008

Published in FSTTCS 2007: Foundations of Software Technology and Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-77050-3_34

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• Planar rectilinear shortest path computation using corridors
• Minimum-link shortest paths for polygons amidst rectilinear obstacles
• Rectilinear Path Problems among Rectilinear Obstacles Revisited
• A nearly optimal algorithm for finding \(L _{1}\) shortest paths among polygonal obstacles in the plane
• Rectilinear shortest paths in the presence of rectangular barriers

Cites work

• An Optimal Algorithm for Euclidean Shortest Paths in the Plane
• An Output-Sensitive Algorithm for Computing Visibility Graphs
• An efficient algorithm for Euclidean shortest paths among polygonal obstacles in the plane
• Constructing the visibility graph for n-line segments in \(O(n^ 2)\) time
• Efficiently Constructing the Visibility Graph of a Simple Polygon with Obstacles
• Rectilinear shortest paths in the presence of rectangular barriers
• TRIANGULATING DISJOINT JORDAN CHAINS
• \(L_ 1\) shortest paths among polygonal obstacles in the plane

Cited in

(4)

• Rectilinear Path Problems among Rectilinear Obstacles Revisited
• An efficient direct approach for computing shortest rectilinear paths among obstacles in a two-layer interconnection model
• Computing skeletons for rectilinearly convex obstacles in the rectilinear plane
• Planar rectilinear shortest path computation using corridors

This page was built for publication: Finding a Rectilinear Shortest Path in R 2 Using Corridor Based Staircase Structures

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5458853)