Roughly speaking, Combinatorial complexes play a similar role in the discrete world as differentiable manifolds in the smooth world. They are able to capture the “intrinsic” properties of a geometric object, i.e. those properties that are independent of any embedding into an ambient space. Combinatorial complexes come in two flavors: cell complexes and simplicial complexes. In this post we deal with the former.
A one-dimensional combinatorial cell complex is the same thing as a finite multigraph. Such a multigraph
- a finite set
of “points”.
- a finite set
of “oriented edges”.
- maps
assigning to each oriented edge its “source point” and its destination point .
- a map
that implements “orientation reversal”: We demand that for all we have and . Moreover we assume
Note that what we call “points” usually would be called “vertices”. We use “points” in order to remain consistent with Houdini terminology. A two-element subset
A typical multigraph looks like this:
You see that there can be several edges connecting the same pair of points and there can be oriented edges whose source and destination point coincide. There also could be isolated points that do not belong to any edge.
A two-dimensional combinatorial cell complex is a one-dimensional cell complex
An edge loop in a one-dimensional cell complex
and
Note that different faces can have the same edge cycle. This is for example the case for the sphere below, which is represented as a two-dimensional cell complex with six points, six edges and two faces:
A two-dimensional combinatorial cell complex
- The points
of a two-dimensional combinatorial cell complex the represent -cells. This cloud of isolated points is called the -skeleton of the cell complex .
- Each edge
corresponds to a copy of the intervall (the unit ball in ). The end points of this 1-cell are identified with the end points of prescribed by the combinatorics. The topological space that results from this gluing is called the -skeleton of .
- Corresponding to each face
we have a -cell , i.e. a copy of the unit disk . The boundary of each -cell is homeomorphic to the unit circle . Up to topological equivalence there is a unique map of to the -skeleton that fits the edge cycle of . The space obtained from gluing in this way the boundaries of all -cells to the 1-skeleton finally is the 2-dimensional cell complex .
See the Wikipedia articles on abstract cell complexes and CW-complexes for further information.
Two-dimensional combinatorial cell complexes are very common in Computer Graphics. In particular, what usually is called a “polygonal surface” is a two-dimensional combinatorial cell complex
Note however that it is not even clear how to render a face