Combinatorial Geometry: Simplicial Complexes

While (for good reasons) we have restricted our treatment of combinatorial cell complexes to the two-dimensional case, the theory of n-dimensional simplicial complexes is rather straightforward:

Definition: A simplicial complex is a finite set P together with a set S of subsets SP with the following properties:

(i) For every iP we have {i}S.

(ii) If SS and TS,T then TS.

An element SS is called a simplex of S of dimension k if the number of its elements equals k+1. The set of all k-dimensional simplices in S is called the k-skeleton Sk of S.

A one-dimensional simplicial complex is the same thing as a graph. The one-dimensional simplices of any simplicial complex are called edges, the two-dimensional simplices are called triangles and the three-dimensional ones are called tetrahedra. The picture below shows a graph with P={1,2,3,4,5,6} and seven edges.

graph

A one-dimensional simplicial complex S (a graph) can be viewed as a special one-dimensional cell complex M (i.e. a special multigraph). The oriented edges of M is the set of ordered pairs (i,j) with {i,j}S1 and the maps s,d,ρ are defined by

s((i,j)):=id((i,j)):=jρ((i,j)):=(j,i).

Similarly, a two-dimensional simplicial complex can be viewed as a special two-dimensional cell complex. The cell-complex below from the last post arises in this way from a two-dimensional simplicial complex with five points, ten edges and six triangles.

tet-cone-simple

We have not really discussed this, but a two-dimensional cell complex describes a unique topological space. The same holds for general simplicial complexes. However, simplicial complexes are much more powerful for the discrete modeling of physical objects for the following reason: The topological space described by a combinatorial simplicial complex comes with a canonical piecewise affine structure. We now elaborate what this means.

Let S be a simplicial complex with point set P. Define then the piecewise affine space C(S) corresponding to S as the set of all functions f:PR such that  f(i)0 for all iP,

iPf(i)=1

and

{iP|f(i)0}S.

For each simplex SS we define an affine space

AS:={g:PR|iPg(i)=1 and iSg(i)=0}

The vector space corresponding to the affine space AS is

VS:={g:PR|pPg(i)=0 and iSg(i)=0}

and each AS is spanned by the simplex

ΣS:={gAS|g(i)0 for all iP}.

The whole space  C(S) is the disjoined union of all the interiors (within AS) of the simplices ΣS for SS. If SS and TS then AT is an affine subspace of AS. Similarly, we also have ΣTΣS in this case.

Each point iP corresponds to a particular element δiC(S) defined by δi(j)=1 for j=i and δi(j)=0 otherwise. We have A{p}=Σ{i}={δi}. The main property that makes simplicial complexes useful for physical modeling is the following easy-to-prove

Theorem: Let S be a simplicial complex with point set P and let  f:PV be a map into any vector space V. Then there is a unique map

f^:C(S)V

whose restriction to each simplex ΣS is affine and which extends f in the sense that for all iP we have

f^(δi)=f(i).

In particular, if we have a two-dimensional simplicial complex and are given a position in R3 for each of its points, it is clear how to fill in the triangles, for example in order to render them.

This entry was posted in Lecture. Bookmark the permalink.

Leave a Reply