Most of the previous ideas generalize nicely for the case of a
polyhedral robot that is capable of translation only in a 3D world
that contains polyhedral obstacles. If and are convex
polyhedra, the resulting
is a convex polyhedron.
Three different types of contact, each of
which generates a different kind of
There are three different kinds of contacts that each lead to half-spaces in :
These are shown in Figure 4.20. Each half-space defines a
face of the polyhedron,
. The representation of
time, in which is the number of
faces of , is the number of faces of , and is the
number of faces of
, which is at most .
- Type FV: A face of and a vertex of
- Type VF: A vertex of and a face of
- Type EE: An edge of and an edge of .
Steven M LaValle