On the shortest paths between two convex polyhedra

Abstract

The problem of computing the Euclidean shortest path between two points in three-dimensional space bounded by a collection of convex and disjoint polyhedral obstacles having n faces altogether is considered. This problem is known to be NP-hard and in exponential time for arbitrarily many obstacles; it can be solved in O ( n ² log n ) time for a single convex polyhedral obstacle and in polynomial time for any fixed number of convex obstacles. In this paper Mount's technique is extended to the case of two convex polyhedral obstacles and an algorithm that solves this problem in time O ( n ³ · 2 O { α ( n ) ⁴ } log n ) (where α ( n ) is the functional inverse of Ackermann's function, and is thus extremely slowly growing) is presented, thus improving significantly Sharir's previous results for this special case. This result is achieved by constructing a new kind of Voronoi diagram, called peeper's Voronoi diagram , which is introduced and analyzed in this paper, and which may be of interest in its own right.