A Nearly Optimal Algorithm for Finding L 1 Shortest Paths among Polygonal Obstacles in the Plane

DOI10.1007/978-3-642-23719-5_41zbMath1346.68229OpenAlexW16724697MaRDI QIDQ3092254

Danny Z. Chen, Haitao Wang

Publication date: 16 September 2011

Published in: Algorithms – ESA 2011 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-23719-5_41

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items (7)

Computing the visibility polygon of an island in a polygonal domain ⋮ An optimal algorithm for minimum-link rectilinear paths in triangulated rectilinear domains ⋮ Computing the \(L_1\) geodesic diameter and center of a polygonal domain ⋮ Visibility and ray shooting queries in polygonal domains ⋮ Quickest visibility queries in polygonal domains ⋮ Computing an \(L_1\) shortest path among splinegonal obstacles in the plane ⋮ Computing Shortest Paths in the Plane with Removable Obstacles

This page was built for publication: A Nearly Optimal Algorithm for Finding L 1 Shortest Paths among Polygonal Obstacles in the Plane