### Shortest paths in the plane with polygonal obstaclesShortest paths in the plane with polygonal obstacles

Access Restriction
Subscribed

 Author Storer, James A. ♦ Reif, John H. Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©1994 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Euclidean plane ♦ Minimal movement problem ♦ Motion planning ♦ Mover's problem ♦ Polygonal obstacles ♦ Robotics ♦ Shortest path Abstract We present a practical algorithm for finding minimum-length paths between points in the Euclidean plane with (not necessarily convex) polygonal obstacles. Prior to this work, the best known algorithm for finding the shortest path between two points in the plane required $\textit{&OHgr;(n2}$ log $\textit{n)}$ time and $\textit{O}(n2)$ space, where $\textit{n}$ denotes the number of obstacle edges. Assuming that a triangulation or a Voronoi diagram for the obstacle space is provided with the input (if is not, either one can be precomputed in $\textit{O}(\textit{n}$ log $\textit{n)}$ time), we present an $\textit{O(kn)}$ time algorithm, where $\textit{k}$ denotes the number of “islands” (connected components) in the obstacle space. The algorithm uses only $\textit{O(n)}$ space and, given a source point $\textit{s},$ produces an $\textit{O(n)}$ size data structure such that the distance between $\textit{s}$ and any other point $\textit{x}$ in the plane $(\textit{x})$ is not necessarily an obstacle vertex or a point on an obstacle edge) can be computed in $\textit{O}(1)$ time. The algorithm can also be used to compute shortest paths for the movement of a disk (so that optimal movement for arbitrary objects can be computed to the accuracy of enclosing them with the smallest possible disk). ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 1994-09-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 41 Issue Number 5 Page Count 31 Starting Page 982 Ending Page 1012

#### Open content in new tab

Source: ACM Digital Library