Structure and Computation of a Class of Piecewise Linear Generalized Voronoi Diagrams with Application 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 d-dimensional polyhedral world. The work is divided into two parts: results for three dimensions and results for general dimensions.

Results in Three Dimensions The data size of the generalized Voronoi diagram in three dimensions is O(n + Ql f), where:

n = total number of 2-faces on the obstacles,

Q = number of obstacles,

f = total number of 2-faces on the moving object.

Analysis shows that the diagram can have several disconnected components within one connected component of the free space, making it unsuitable for motion planning.

This occurs if and only if a polytope of the Voronoi complex contains one or more polytopes in its relative interior.

Several structural properties of the diagram are proved.

Results in General Dimensions For general dimensions, the size of the diagram is shown to depend on:

n = data size of the obstacles,

f = data size of the moving object.

The diagram’s complexity is analyzed, and structural properties are established.

Algorithmic Contributions An easy-to-implement algorithm is proposed for constructing the diagram using the established structural properties.

The complexity of this algorithm is O(g(d)(n + Ql)e + logQ) time, where:

g(d) is a singly exponential function of dimension d,

e is the maximum facet number across all dimensions in the Voronoi complex.

A simple and elegant algorithm is further proposed to make the diagram suitable for motion planning.