Planar rectilinear shortest path computation using corridors

DOI10.1016/j.comgeo.2009.02.005zbMath1175.65032OpenAlexW2021380525MaRDI QIDQ833714

Sanjiv Kapoor, Rajasekhar Inkulu

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)

Related Items (9)

Routing among convex polygonal obstacles in the plane ⋮ Computing \(L_1\) shortest paths among polygonal obstacles in the plane ⋮ On finding a shortest isothetic path and its monotonicity inside a digital object ⋮ Computing the visibility polygon of an island in a polygonal domain ⋮ Computing the \(L_1\) geodesic diameter and center of a polygonal domain ⋮ Visibility and ray shooting queries in polygonal domains ⋮ Unnamed Item ⋮ Computing an \(L_1\) shortest path among splinegonal obstacles in the plane ⋮ Computing Shortest Paths in the Plane with Removable Obstacles

Cites Work

• Constructing the visibility graph for n-line segments in \(O(n^ 2)\) time
• Rectilinear shortest paths in the presence of rectangular barriers
• \(L_ 1\) shortest paths among polygonal obstacles in the plane
• On parallel rectilinear obstacle-avoiding paths
• Rectilinear short path queries among rectangular obstacles
• An efficient algorithm for Euclidean shortest paths among polygonal obstacles in the plane
• Algorithms for Reporting and Counting Geometric Intersections
• On Vertical Visibility in Arrangements of Segments and the Queue Size in the Bentley-Ottmann Line Sweeping Algorithm
• An Output-Sensitive Algorithm for Computing Visibility Graphs
• An Optimal Algorithm for Euclidean Shortest Paths in the Plane
• ORTHOGONAL SHORTEST ROUTE QUERIES AMONG AXES PARALLEL RECTANGULAR OBSTACLES
• TRIANGULATING DISJOINT JORDAN CHAINS
• Efficiently Constructing the Visibility Graph of a Simple Polygon with Obstacles
• Planar spanners and approximate shortest path queries among obstacles in the plane
• Efficient approximate shortest-path queries among isothetic rectangular obstacles
• Finding a Rectilinear Shortest Path in R 2 Using Corridor Based Staircase Structures

This page was built for publication: Planar rectilinear shortest path computation using corridors