An efficient algorithm for Euclidean shortest paths among polygonal obstacles in the plane

DOI10.1007/PL00009323zbMath0892.68047DBLPjournals/dcg/KapoorMM97WikidataQ29397229 ScholiaQ29397229MaRDI QIDQ1380799

S. N. Maheshwari, Sanjiv Kapoor, Joseph S. B. Mitchell

Publication date: 11 March 1998

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

zbMATH Keywords

shortest path

Mathematics Subject Classification ID

Parallel algorithms in computer science (68W10) Mathematical problems of computer architecture (68M07)

Related Items (28)

Visibility queries in a polygonal region ⋮ Planar rectilinear shortest path computation using corridors ⋮ Touring a sequence of disjoint polygons: complexity and extension ⋮ Rectilinear short path queries among rectangular obstacles ⋮ Routing among convex polygonal obstacles in the plane ⋮ Navigating Weighted Regions with Scattered Skinny Tetrahedra ⋮ KINETIC COLLISION DETECTION FOR SIMPLE POLYGONS ⋮ An algorithmic approach to some problems in terrain navigation ⋮ A multifacility location problem on median spaces ⋮ Routing in polygonal domains ⋮ Computing \(L_1\) shortest paths among polygonal obstacles in the plane ⋮ Visiting a Polygon on the Optimal Way to a Query Point ⋮ Shortest Path Queries in Polygonal Domains ⋮ Maximal distortion of geodesic diameters in polygonal domains ⋮ Shortest path planning for a tethered robot ⋮ On maximum flows in polyhedral domains ⋮ 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 ⋮ Honey-pot constrained searching with local sensory information ⋮ Finding a Rectilinear Shortest Path in R 2 Using Corridor Based Staircase Structures ⋮ EXACT AND APPROXIMATION ALGORITHMS FOR FINDING AN OPTIMAL BRIDGE CONNECTING TWO SIMPLE POLYGONS ⋮ Minimizing Distance-to-Sight in Polygonal Domains ⋮ Quickest visibility queries in polygonal domains ⋮ Computing an \(L_1\) shortest path among splinegonal obstacles in the plane ⋮ Visibility polygons and visibility graphs among dynamic polygonal obstacles in the plane ⋮ Routing in Polygonal Domains

This page was built for publication: An efficient algorithm for Euclidean shortest paths among polygonal obstacles in the plane