Finding shortest paths in the presence of orthogonal obstacles using a combined L 1 and link metric

DOI10.1007/3-540-52846-6_91MaRDI QIDQ5056105zbMATH OpenOpenAlexFDO

Authors Bengt J. Nilsson, Mark de Berg, Marc Van Kreveld, Mark H. Overmars

Publication date 9 December 2022

Published in SWAT 90 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-52846-6_91

Mathematics Subject Classification ID

Data structures (68P05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• A nearly optimal algorithm for finding \(L _{1}\) shortest paths among polygonal obstacles in the plane
• Computing \(L_1\) shortest paths among polygonal obstacles in the plane
• \(L_1\) shortest path queries among polygonal obstacles in the plane
• Two-point \(L_1\) shortest path queries in the plane
• \(L_ 1\) shortest paths among polygonal obstacles in the plane

Cites work

• A note on two problems in connexion with graphs
• An \(O(n \log n)\) algorithm for computing a link center in a simple polygon
• Computing the link center of a simple polygon
• Euclidean shortest paths in the presence of rectilinear barriers
• Finding minimum rectilinear distance paths in the presence of barriers
• Fractional cascading. I: A data structuring technique
• Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes
• On Shortest Paths in Polyhedral Spaces
• Rectilinear shortest paths in the presence of rectangular barriers
• Some methods of computational geometry applied to computer graphics

Cited in

(7)

• An optimal algorithm for constructing an optimal bridge between two simple rectilinear polygons
• Computing minimum length paths of a given homotopy class
• Estimation and determination of shortest path length in a road network with obstacles
• The Length of Shortest Vertex Paths in Binary Occupancy Grids Compared to Shortest r-Constrained Ones
• Computing a maxian point of a simple rectilinear polygon
• A discretization result for some optimization problems in framework spaces with polyhedral obstacles and the Manhattan metric
• On finding a shortest isothetic path and its monotonicity inside a digital object

This page was built for publication: Finding shortest paths in the presence of orthogonal obstacles using a combined L 1 and link metric

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5056105)