Rectilinear shortest paths in the presence of rectangular barriers
From MaRDI portal
Publication:1109046
DOI10.1007/BF02187714zbMath0655.05041MaRDI QIDQ1109046
Publication date: 1989
Published in: Discrete \& Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://eudml.org/doc/131063
barriers; planar subdivision; rectangular regions; query point; shortest-path problem; isothetic rectangles; sweep technique
68Q25: Analysis of algorithms and problem complexity
05C35: Extremal problems in graph theory
05C38: Paths and cycles
Related Items
A SHORTEST PAIR OF PATHS ON THE PLANE WITH OBSTACLES AND CROSSING AREAS, On graphs preserving rectilinear shortest paths in the presence of obstacles, Parallel rectilinear shortest paths with rectangular obstacles, On parallel rectilinear obstacle-avoiding paths, Computing minimum length paths of a given homotopy class, Rectilinear short path queries among rectangular obstacles, Optimal parallel algorithms for rectilinear link-distance problems, A multifacility location problem on median spaces, \(L_ 1\)-embeddability of rectilinear polygons with holes, Rectilinear paths among rectilinear obstacles, An optimal algorithm for rectilinear steiner trees for channels with obstacles