An Efficient Algorithm for Euclidean Shortest Paths Among Polygonal Obstacles in the Plane

• DOI: 10.1007/pl00009323
• Publication Date: 2006-04-11T11:30:34Z
• Authors: S. Kapoor; S. N. Maheshwari; J. S. B. Mitchell
• Keywords: 0211 other engineering and technologies; 0102 computer and information sciences; 02 engineering and technology; 01 natural sciences

We give an algorithm to compute a (Euclidean) shortest path in a polygon with h holes and a total of n vertices. The algorithm uses O(n) space and requires $O(n+h^2\log n)$ time.