An O(n2) shortest path algorithm for a non-rotating convex body

DOI10.1016/0196-6774(88)90003-XzbMath0647.68048OpenAlexW1980453746MaRDI QIDQ3792242

Leonidas J. Guibas, J. E. Hershberger

Publication date: 1988

Published in: Journal of Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0196-6774(88)90003-x

zbMATH Keywords

shortest pathpath graphcomputational geometrypolygonal obstaclesmoving a convex bodytangent-visibility

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Convex sets in (2) dimensions (including convex curves) (52A10)

Related Items (4)

Computing the intersection-depth to polyhedra ⋮ Obstacle growing in a nonpolygonal world ⋮ On fast planning of suboptimal paths amidst polygonal obstacles in plane ⋮ A Near-Optimal Algorithm for Shortest Paths Among Curved Obstacles in the Plane

This page was built for publication: An O(n2) shortest path algorithm for a non-rotating convex body