Citation
Jh. Reif et Ja. Storer, SINGLE-EXPONENTIAL UPPER BOUND FOR FINDING SHORTEST PATHS IN 3 DIMENSIONS, Journal of the Association for Computing Machinery, 41(5), 1994, pp. 1013-1019
Citations number
22
Categorie Soggetti
Computer Sciences","Computer Science Hardware & Architecture
Journal title
Journal of the Association for Computing Machinery
ISSN journal
00045411
→ ACNP
Volume
41
Issue
5
Year of publication
1994
Pages
1013 - 1019
Database
ISI
SICI code
Abstract
We derive a single-exponential time upper bound for finding the shorte
st path between two points in 3-dimensional Euclidean space with (nonn
ecessarily convex) polyhedral obstacles. Prior to this work, the best
known algorithm required double-exponential time. Given that the probl
em is known to be PSPACE-hard, the bound we present is essentially the
best (in the worst-case sense) that can reasonably be expected.