Computing Homotopic Shortest Paths Efficiently

2002/04/25 by Alon Efrat, Stephen Kobourov, Stephen G. Kobourov +4
Computer Science · #Computational Geometry and Mesh Generation #Data Management and Algorithms #Topological and Geometric Data Analysis #cs.CG

paper · pdf · doi:10.48550/arxiv.cs/0204050

12 pages, 11 figures

arxiv created 2002/04/25 · arxiv updated 2009/11/30

Abstract

This paper addresses the problem of finding shortest paths homotopic to a given disjoint set of paths that wind amongst point obstacles in the plane. We present a faster algorithm than previously known.

Related

• Shortest Paths Among Obstacles in the Plane Revisited
• A New Algorithm for Euclidean Shortest Paths in the Plane
• Computing L1 Shortest Paths among Polygonal Obstacles in the Plane
• A Homotopy Invariant Based on Convex Dissection Topology and a Distance Optimal Path Planning Algorithm
• Efficient Search of the k Shortest Non-Homotopic Paths by Eliminating Non-k-Optimal Topologies