##

6.3.1 General Definitions

In this section, the term *complex* refers to a collection of
cells together with their boundaries. A partition into cells can be
derived from a complex, but the complex contains additional
information that describes how the cells must fit together. The term
*cell decomposition* still refers to the partition of the space
into cells, which is derived from a *complex*.

It is tempting to define complexes and cell decompositions in a very
general manner. Imagine that any partition of
could be
called a cell decomposition. A cell could be so complicated that the
notion would be useless. Even
itself could be declared as
one big cell. It is more useful to build decompositions out of
simpler cells, such as ones that contain no holes. Formally, this
requires that every -dimensional cell is homeomorphic to
, an open -dimensional unit ball. From a motion
planning perspective, this still yields cells that are quite
complicated, and it will be up to the particular cell decomposition
method to enforce further constraints to yield a complete planning
algorithm.

Two different complexes will be introduced. The *simplicial
complex* is explained because it is one of the easiest to understand.
Although it is useful in many applications, it is not powerful enough
to represent all of the complexes that arise in motion planning.
Therefore, the *singular complex* is also introduced. Although it
is more complicated to define, it encompasses all of the cell
complexes that are of interest in this book. It also provides an
elegant way to represent topological spaces. Another important cell
complex, which is not covered here, is the *CW-complex*
[439].

**Subsections**
Steven M LaValle
2012-04-20