Planar rectilinear shortest path computation using corridors
type: Item
instance of: scholarly article
title: Planar rectilinear shortest path computation using corridors
zbMATH Open document ID: 1175.65032
author: Rajasekhar Inkulu
author: Sanjiv Kapoor
published in: Computational Geometry
publication date: 2009-08-14T00:00:00Z
review text: 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)].
reviewed by: H. P. Dikshit
Mathematics Subject Classification ID: 65D18
Mathematics Subject Classification ID: 68U05
zbMATH DE Number: 5595373
zbMATH Keywords: shortest path computation
zbMATH Keywords: polygonal regions
zbMATH Keywords: polygonal obstacles
zbMATH Keywords: algorithm
zbMATH Keywords: visibility graph
MaRDI profile type: Publication
full work available at URL: j.comgeo.2009.02.005
OpenAlex ID: W2021380525
cites work: Planar spanners and approximate shortest path queries among obstacles in the plane
cites work: On parallel rectilinear obstacle-avoiding paths
cites work: TRIANGULATING DISJOINT JORDAN CHAINS
cites work: Algorithms for Reporting and Counting Geometric Intersections
cites work: Rectilinear short path queries among rectangular obstacles
cites work: Rectilinear shortest paths in the presence of rectangular barriers
cites work: ORTHOGONAL SHORTEST ROUTE QUERIES AMONG AXES PARALLEL RECTANGULAR OBSTACLES
cites work: An Output-Sensitive Algorithm for Computing Visibility Graphs
cites work: An Optimal Algorithm for Euclidean Shortest Paths in the Plane
cites work: Finding a Rectilinear Shortest Path in R 2 Using Corridor Based Staircase Structures
cites work: Efficiently Constructing the Visibility Graph of a Simple Polygon with Obstacles
cites work: An efficient algorithm for Euclidean shortest paths among polygonal obstacles in the plane
cites work: \(L_ 1\) shortest paths among polygonal obstacles in the plane
cites work: Efficient approximate shortest-path queries among isothetic rectangular obstacles
cites work: On Vertical Visibility in Arrangements of Segments and the Queue Size in the Bentley-Ottmann Line Sweeping Algorithm
cites work: Constructing the visibility graph for n-line segments in \(O(n^ 2)\) time
DOI: 10.1016/J.COMGEO.2009.02.005
description: scientific article; zbMATH DE number 5595373