3-dimensional shortest paths in the presence of polyhedral obstacles


Journal Article

© Springer-Verlag Berlin Heidelberg 1988. 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 nk0(1) time and also one that runs in O(nlog(k)) space.

Full Text

Duke Authors

Cited Authors

  • Reif, JH; Storer, JA

Published Date

  • January 1, 1988

Published In

Volume / Issue

  • 324 LNCS /

Start / End Page

  • 85 - 92

Electronic International Standard Serial Number (EISSN)

  • 1611-3349

International Standard Serial Number (ISSN)

  • 0302-9743

Digital Object Identifier (DOI)

  • 10.1007/BFb0017133

Citation Source

  • Scopus