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 ${\cal C}_{free}$ could be called a cell decomposition. A cell could be so complicated that the notion would be useless. Even ${\cal C}_{free}$ 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 $k$-dimensional cell is homeomorphic to $B^k \subset {\mathbb{R}}^k$, an open $k$-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].