A near-optimal algorithm for shortest paths among curved obstacles in the plane

DOI10.1145/2462356.2462374zbMath1305.68239OpenAlexW2130647774MaRDI QIDQ5174496

Hakan Yildiz, Subhash Suri, J. E. Hershberger

Publication date: 17 February 2015

Published in: Proceedings of the twenty-ninth annual symposium on Computational geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2462356.2462374

zbMATH Keywords

shortest pathspolygonizationcurved obstaclescontinuous dijkstra

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (5)

Navigating Weighted Regions with Scattered Skinny Tetrahedra ⋮ Shortest paths in the plane with obstacle violations ⋮ Visibility graphs, dismantlability, and the cops and robbers game ⋮ Unnamed Item ⋮ Computing an \(L_1\) shortest path among splinegonal obstacles in the plane

This page was built for publication: A near-optimal algorithm for shortest paths among curved obstacles in the plane