Planar rectilinear shortest path computation using corridors

DOI10.1016/J.COMGEO.2009.02.005MaRDI QIDQ833714zbMATH OpenOpenAlexFDO

Authors Rajasekhar Inkulu, Sanjiv Kapoor

Publication date 14 August 2009

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.comgeo.2009.02.005

zbMATH Keywords

algorithmvisibility graphpolygonal obstaclespolygonal regionsshortest path computation

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18)

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

• Algorithms for Reporting and Counting Geometric Intersections
• 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
• 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
• ORTHOGONAL SHORTEST ROUTE QUERIES AMONG AXES PARALLEL RECTANGULAR OBSTACLES
• On Vertical Visibility in Arrangements of Segments and the Queue Size in the Bentley-Ottmann Line Sweeping Algorithm
• On parallel rectilinear obstacle-avoiding paths
• 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
• \(L_ 1\) shortest paths among polygonal obstacles in the plane

Cited in

(19)

• Routing among convex polygonal obstacles in the plane
• Computing skeletons for rectilinearly convex obstacles in the rectilinear plane
• An algorithm for finding shortest paths in a maze
• Path planning in a weighted planar subdivision under the Manhattan metric
• Computing a rectilinear shortest path amid splinegons in plane
• Finding a region with the minimum total \(L_1\) distance from prescribed terminals
• Computing an \(L_1\) shortest path among splinegonal obstacles in the plane
• Routing among convex polygonal obstacles in the plane
• Computing shortest paths in the plane with removable obstacles
• Finding a Rectilinear Shortest Path in R 2 Using Corridor Based Staircase Structures
• Characterizing the shortest path of an object among obstacles
• scientific article; zbMATH DE number 7559259 (Why is no real title available?)
• On finding a shortest isothetic path and its monotonicity inside a digital object
• Computing \(L_1\) shortest paths among polygonal obstacles in the plane
• Computing the \(L_1\) geodesic diameter and center of a polygonal domain
• Finding a shortest pair of paths on the plane with obstacles and crossing areas
• Computing the visibility polygon of an island in a polygonal domain
• Visibility and ray shooting queries in polygonal domains
• An efficient direct approach for computing shortest rectilinear paths among obstacles in a two-layer interconnection model

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)