Shortest paths in the plane with polygonal obstacles

DOI10.1145/185675.185795zbMath0814.68129OpenAlexW1985010089MaRDI QIDQ4323731

James A. Storer, John H. Reif

Publication date: 22 June 1995

Published in: Journal of the ACM (Search for Journal in Brave)

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

zbMATH Keywords

Voronoi diagramminimum-length paths

Mathematics Subject Classification ID

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

Related Items (12)

Routing among convex polygonal obstacles in the plane ⋮ ALGORITHMS FOR DISTANCE PROBLEMS IN PLANAR COMPLEXES OF GLOBAL NONPOSITIVE CURVATURE ⋮ Routing in polygonal domains ⋮ Approximate distance oracles for graphs with dense clusters ⋮ Shortest paths in the plane with obstacle violations ⋮ Computing \(L_1\) shortest paths among polygonal obstacles in the plane ⋮ A Near-Optimal Algorithm for Shortest Paths Among Curved Obstacles in the Plane ⋮ Approximate Shortest Paths in Polygons with Violations ⋮ An algorithm for finding the shortest sailing distance from any maritime navigable point to a designated port ⋮ Unnamed Item ⋮ Computing an \(L_1\) shortest path among splinegonal obstacles in the plane ⋮ Routing in Polygonal Domains

This page was built for publication: Shortest paths in the plane with polygonal obstacles