A near optimal algorithm for finding Euclidean shortest path in polygonal domain

2010/11/30 by R. Inkulu, Inkulu, Rajasekhar, Sanjiv Kapoor +3 · 3 citations
Computer Science · #Computational Geometry and Mesh Generation #Data Management and Algorithms #Robotic Path Planning Algorithms

paper · pdf · doi:10.48550/arxiv.1011.6481

Abstract

We present an algorithm to find an \it Euclidean Shortest Path from a source vertex s to a sink vertex t in the presence of obstacles in \Re². Our algorithm takes O(T+m(\lgm)(\lgn)) time and O(n) space. Here, O(T) is the time to triangulate the polygonal region, m is the number of obstacles, and n is the number of vertices. This bound is close to the known lower bound of O(n+m\lgm) time and O(n) space. Our approach involve progressing shortest path wavefront as in continuous Dijkstra-type method, and confining its expansion to regions of interest.

Cited by

• A New Algorithm for Euclidean Shortest Paths in the Plane
• Two-Point L₁ Shortest Path Queries in the Plane
• Shortest Paths Among Obstacles in the Plane Revisited

Related

• A New Algorithm for Euclidean Shortest Paths in the Plane
• Approximate Euclidean shortest paths in polygonal domains
• Computing L1 Shortest Paths among Polygonal Obstacles in the Plane
• Shortest Paths Among Obstacles in the Plane Revisited
• An Efficient Algorithm for Computing High-Quality Paths amid Polygonal Obstacles