Shortest Paths in the Plane with Polygonal Obstacles


Journal Article

We present a practical algorithm for finding minimum-length paths between points in the Euclidean plane with 1994 polygonal obstacles. Prior to this work, the best known algorithm for finding the shortest path between two points in the plane required (n2 log n) time and O(n2) space, where 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 O(n log n) time), we present an O(kn) time algorithm, where k denotes the number of “islands” (connected components) in the obstacle space. The algorithm uses only O(n) space and, given a source point s, produces an O(n) size data structure such that the distance between s and any other point x in the plane (x) is not necessarily an obstacle vertex or a point on an obstacle edge) can be computed in 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). © 1994, ACM. All rights reserved.

Full Text

Duke Authors

Cited Authors

  • Storer, JA; Reif, JH

Published Date

  • January 9, 1994

Published In

Volume / Issue

  • 41 / 5

Start / End Page

  • 982 - 1012

Electronic International Standard Serial Number (EISSN)

  • 1557-735X

International Standard Serial Number (ISSN)

  • 0004-5411

Digital Object Identifier (DOI)

  • 10.1145/185675.185795

Citation Source

  • Scopus