A Single-Exponential Upper Bound for Finding Shortest Paths in Three Dimensions


Journal Article

We derive a single-exponential time upper bound for finding the shortest path between two points in 3-dimensional Euclidean space with 1994 polyhedral obstacles. Prior to this work, the best known algorithm required double-exponential time. Given that the problem is known to be PSPACE-hard, the bound we present is essentially the best (in the worst-case sense) that can reasonably be expected. © 1994, ACM. All rights reserved.

Full Text

Duke Authors

Cited Authors

  • Reif, JH; Storer, JA

Published Date

  • January 9, 1994

Published In

Volume / Issue

  • 41 / 5

Start / End Page

  • 1013 - 1019

Electronic International Standard Serial Number (EISSN)

  • 1557-735X

International Standard Serial Number (ISSN)

  • 0004-5411

Digital Object Identifier (DOI)

  • 10.1145/185675.185811

Citation Source

  • Scopus