Publications [#331474] of John H. Reif

Journal articles or Book chapters PUBLISHED

1. Reif, JH; Storer, JA, 3-dimensional shortest paths in the presence of polyhedral obstacles, Lecture Notes in Computer Science Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics, vol. 324 LNCS (January, 1988), pp. 85-92, Springer Verlag [doi]
   (last updated on 2026/01/15)

   Abstract:
   We consider the problem of finding a minimum length path between two points in 3-dimensional Euclidean space which avoids a set of (not necessarily convex) polyhedral obstacles; we let n denote the number of the obstacle edges and k denote the number of "islands" in the obstacle space. An island is defined to be a maximal convex obstacle surface such that for any two points contained in the interior of the island, a minimal length path between these two points is strictly contained in the interior of the island; for example, a set of i disconnected convex polyhedra forms a set of i islands, however, a single non-convex polyhedron will constitute more that one island. Prior to this work, the best known algorithm required double-exponential time. We present an algorithm that runs in n^k0(1) time and also one that runs in O(n^log(k)) space.