Efficient algorithms for Euclidean shortest path and visibility problems with polygonal obstacles

摘要

The problem of determining the Euclidean shortest path between two points in the presence of m simple polygonal obstacles is studied. An O( m2 logn + nlogn ) algorithm is developed, where n is the total number of points in the obstacles. A simple O(E+T) algorithm for determining the visibility graph is also shown, where E is the number of visibility edges and T is the time for triangulating the point set. This is extended to a O(Es + nlogn) algorithm for the shortest path problem where Es is bounded by m2.