Efficient algorithms for Euclidean shortest path and visibility problems with polygonal obstacles
S Kapoor, SN Maheshwari - … of the fourth annual symposium on …, 1988 - dl.acm.org
S Kapoor, SN Maheshwari
Proceedings of the fourth annual symposium on computational geometry, 1988•dl.acm.orgThe 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.
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.
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.
ACM Digital Library