Access Restriction

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

   Open content in new tab
Source: ACM Digital Library