Skip to main content

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

Publication ,  Journal Article
Reif, JH; Storer, JA
Published in: Journal of the ACM (JACM)
January 9, 1994

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.

Duke Scholars

Published In

Journal of the ACM (JACM)

DOI

EISSN

1557-735X

ISSN

0004-5411

Publication Date

January 9, 1994

Volume

41

Issue

5

Start / End Page

1013 / 1019

Related Subject Headings

  • Computation Theory & Mathematics
  • 46 Information and computing sciences
  • 08 Information and Computing Sciences
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Reif, J. H., & Storer, J. A. (1994). A Single-Exponential Upper Bound for Finding Shortest Paths in Three Dimensions. Journal of the ACM (JACM), 41(5), 1013–1019. https://doi.org/10.1145/185675.185811
Reif, J. H., and J. A. Storer. “A Single-Exponential Upper Bound for Finding Shortest Paths in Three Dimensions.” Journal of the ACM (JACM) 41, no. 5 (January 9, 1994): 1013–19. https://doi.org/10.1145/185675.185811.
Reif JH, Storer JA. A Single-Exponential Upper Bound for Finding Shortest Paths in Three Dimensions. Journal of the ACM (JACM). 1994 Jan 9;41(5):1013–9.
Reif, J. H., and J. A. Storer. “A Single-Exponential Upper Bound for Finding Shortest Paths in Three Dimensions.” Journal of the ACM (JACM), vol. 41, no. 5, Jan. 1994, pp. 1013–19. Scopus, doi:10.1145/185675.185811.
Reif JH, Storer JA. A Single-Exponential Upper Bound for Finding Shortest Paths in Three Dimensions. Journal of the ACM (JACM). 1994 Jan 9;41(5):1013–1019.

Published In

Journal of the ACM (JACM)

DOI

EISSN

1557-735X

ISSN

0004-5411

Publication Date

January 9, 1994

Volume

41

Issue

5

Start / End Page

1013 / 1019

Related Subject Headings

  • Computation Theory & Mathematics
  • 46 Information and computing sciences
  • 08 Information and Computing Sciences