Rectilinear shortest paths in the presence of rectangular barriers
From MaRDI portal
Publication:1109046
DOI10.1007/BF02187714zbMath0655.05041OpenAlexW1992320342MaRDI QIDQ1109046
Publication date: 1989
Published in: Discrete \& Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://eudml.org/doc/131063
barriersplanar subdivisionrectangular regionsquery pointshortest-path problemisothetic rectanglessweep technique
Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Paths and cycles (05C38)
Related Items
Minimum-link shortest paths for polygons amidst rectilinear obstacles, Computing minimum length paths of a given homotopy class, Spatial Distribution of Traffic Flow in a Rectangular City with a Grid Network and a Rectangular Barrier, Planar rectilinear shortest path computation using corridors, Finding shortest paths in the presence of orthogonal obstacles using a combined L 1 and link metric, Rectilinear short path queries among rectangular obstacles, An optimal algorithm for rectilinear steiner trees for channels with obstacles, Efficient approximate shortest-path queries among isothetic rectangular obstacles, Optimal parallel algorithms for rectilinear link-distance problems, An algorithmic approach to some problems in terrain navigation, A multifacility location problem on median spaces, \(L_ 1\)-embeddability of rectilinear polygons with holes, Computing \(L_1\) shortest paths among polygonal obstacles in the plane, An efficient algorithm for shortest paths in vertical and horizontal segments, Path planning in a weighted planar subdivision under the Manhattan metric, Enumerating Grid Layouts of Graphs, Geometric path problems with violations, On graphs preserving rectilinear shortest paths in the presence of obstacles, Parallel rectilinear shortest paths with rectangular obstacles, An optimal algorithm for minimum-link rectilinear paths in triangulated rectilinear domains, Lower bounds for computing geometric spanners and approximate shortest paths, Finding a Rectilinear Shortest Path in R 2 Using Corridor Based Staircase Structures, Rectilinear paths among rectilinear obstacles, Computing an \(L_1\) shortest path among splinegonal obstacles in the plane, Unnamed Item, On parallel rectilinear obstacle-avoiding paths, On rectilinear link distance, A SHORTEST PAIR OF PATHS ON THE PLANE WITH OBSTACLES AND CROSSING AREAS, Rectilinear path problems in restricted memory setup
Cites Work
- Unnamed Item
- A note on two problems in connexion with graphs
- Constructing the visibility graph for n-line segments in \(O(n^ 2)\) time
- Visibility of disjoint polygons
- On the computational complexity and geometry of the first-order theory of the reals. III: Quantifier elimination
- Euclidean shortest paths in the presence of rectilinear barriers
- Optimal Point Location in a Monotone Subdivision
- On Shortest Paths in Polyhedral Spaces
- Finding minimum rectilinear distance paths in the presence of barriers
