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

DOI10.1007/3-540-52846-6_91zbMath1502.68314OpenAlexW1932623398MaRDI QIDQ5056105

Bengt J. Nilsson, Marc J. van Kreveld, Mark H. Overmars, Mark T. de Berg

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

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

Related Items (max. 100)

Computing minimum length paths of a given homotopy class ⋮ Computing a maxian point of a simple rectilinear polygon ⋮ On finding a shortest isothetic path and its monotonicity inside a digital object ⋮ A discretization result for some optimization problems in framework spaces with polyhedral obstacles and the Manhattan metric ⋮ An optimal algorithm for constructing an optimal bridge between two simple rectilinear polygons

Cites Work

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

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