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