Publications [#237114] of John H. Reif

Journal articles or Book chapters PUBLISHED

1. Reif, JH; Storer, JA, A Single-Exponential Upper Bound for Finding Shortest Paths in Three Dimensions, Journal of the ACM Jacm, vol. 41 no. 5 (January, 1994), pp. 1013-1019, Association for Computing Machinery (ACM) [pdf], [doi]
   (last updated on 2026/01/15)

   Abstract:
   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.