Structure and computation of a class of piece wise linear generalized voronoi diagrams with applications to translational motion planning

Abstract

This thesis concerns the development of a piecewise linear generalized Voronoi diagram and its application for translating a convex polytope among convex polyhedra in a general r r-dimensional polyhedral world. This work is divided into two parts: the results for three dimensions and the results for general dimensions.

First, it is shown that the data size of this generalized Voronoi diagram for three dimensions is O(nQl) O(nQ l ), where n n is the total number of 2-faces on the obstacles, Q Q is the number of obstacles, and l l is the total number of 2-faces on the moving object. For general dimensions, it is shown that the size of the diagram is O(nQl) O(nQ l ), where n n is the data size of the obstacles, and l l is the data size of the moving object.

It is shown that this diagram can have several disconnected components in one connected component of the free space and is thus unsuitable for motion planning. An analysis of the diagram is done, and it is established that this happens if and only if the following simple geometric structure occurs in the diagram: a polytope of the Voronoi complex contains one or more polytopes in its relative interior. Also, some structural properties of this diagram are proved.

We propose an easy-to-implement algorithm which uses these properties for the construction of this diagram. The complexity of this algorithm is O(g(d)(n+Ql)e+log?Q) O(g(d)(n+Ql)e+logQ) time, where g(d) g(d) is a singly exponential function of d d and e e is the maximum over all dimensional facet numbers on the Voronoi complex. A simple and elegant algorithm is proposed to make the diagram suitable for motion planning.