On shortest paths amidst convex polyhedra

ABSTRACT

We consider the problem of computing the Euclidean shortest path between two points in three-dimensional space which must avoid the interiors of k given disjoint convex polyhedral obstacles, having altogether n faces. Although this problem is hard to solve when k is arbitrarily large, it had been efficiently solved by Mount [Mo84] (cf. also Sharir and Schorr [SS84]) for k = 1, i.e. in the presence of a single convex polyhedral obstacle, in time &Ogr;(n2log n). In this paper we consider the generalization of this technique to the cases k = 2 and k > 2. In the first part of this presentation we describe an algorithm which calculates shortest paths amidst two convex polyhedral obstacles in time &Ogr;(n3&agr;(n)&Ogr;(&agr;(n)7)log n), where &agr;(n) is the functional inverse of Ackermann's function (and is thus extremely slowly growing). This result is achieved by constructing a new kind of Voronoi diagram, called peeper's Voronoi diagram, which is introduced and analyzed here. In the second part we show that shortest paths amidst k > 2 disjoint convex polyhedral obstacles can be calculated in time polynomial in the total number n of faces of these obstacles (but exponential in the number of obstacles). This is a consequence of the following result: Let K be a 3-D convex polyhedron having n vertices. Then the number of shortest-path edge sequences on K is polynomial in n (specifically &Ogr;(n7)), where a shortest-path edge sequence &xgr; is a sequence of edges of K for which there exist two points X, Y on the surface S of K such that &xgr; is the sequence of edges crossed by the shortest path from X to Y along S.

REFERENCES

• BS85: A. Baltsan and M. Sharir, On shortest paths between two convex polyhedra, Tech. Rept. 180, Comp. Sci. Dept., Courant Institute, September 1985.
• HS84: S. Hart arid M. Sharir, Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes, Tech. Rept. 84-011, The Eskenasy Institute of Computer Sciences, Tel Aviv University, August 1984 (also to appear in Combinatorica.)
• Mo84: D.M. Mount, On finding shortest paths on convex polyhedra, Tech. Rept., Computer Science Department, University of Maryland, October 1984.
• RS85: J.H. Reff and j.A. Storer, Shortest paths in Euclidean space with polyhedral obstacles, Tech. Rept. CS-85-121, Computer Science Dept., Brandeis University, Waltham, Mass., April 1985.
• Sh85a: M. Sharir, Almost linear upper bounds on the length of general Davenport-Schinzel sequences, Tech. Rept. 85-029, The Eskenasy Institute of Computer Sciences, Tel Aviv University, February 1985.
• Sh85b: M. Sharir, On shortest paths amidst convex polyhedra, Tech. Rept. 181, Comp. Sci. Dept., Courant Institute, September 1985.
• SS84: M. Sharir and A. Sehorr, On shortest paths in polyhedral spaces, Tech. Rept. 84-001, The Eskenasy Institute of Computer Sciences, Tel Aviv University, March 1984. (also to appear in SIAM J. Computing.)
• Sz74: E. Szemeredi, On a problem by Davenport and Schinzel, Acta Arithmetica 25 (1974) pp. 213-224.

INDEX TERMS

Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Linear programming
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Path and circuit problems

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling

General Terms:
Algorithms, Performance, Theory, Verification