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 $\mathcal{S}$ of subsets $S\subset P$ with the following properties:

(i) For every $i\in P$ we have $\{i\}\in \mathcal{S}$.

(ii) If $S\in\mathcal{S}$ and $T\subset S,\,T\neq \emptyset$ then $T\in \mathcal{S}$.

An element $S\in\mathcal{S}$ is called a simplex of $\mathcal{S}$ of dimension $k$ if the number of its elements equals $k+1$. The set of all $k$-dimensional simplices in $\mathcal{S}$ is called the $k$-skeleton $\mathcal{S}^k$ of $\mathcal{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 $\mathcal{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\}\in \mathcal{S}^1$ and the maps $s,d,\rho$ are defined by

\begin{align*}s((i,j))&:=i\\ d((i,j))&:=j \\ \rho((i,j))&:=(j,i).\end{align*}

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 $\mathcal{S}$ be a simplicial complex with point set $P$. Define then the piecewise affine space $C(\mathcal{S})$ corresponding to $\mathcal{S}$ as the set of all functions $f:P\to \mathbb{R}$ such that  $f(i)\geq 0$ for all $i\in P$,

$$\sum_{i\in P}\, f(i)=1$$

and

$$\big\{ \,i\in P \,\,\,\big|\,\,\, f(i)\neq 0\,\big\} \in \mathcal{S}.$$

For each simplex $S\in \mathcal{S}$ we define an affine space

$$\mathcal{A}_S:= \bigg\{\, g: P\to \mathbb{R} \,\,\,\bigg|\,\,\,\sum_{i\in P} g(i)=1\mbox{   and   }i\notin S \implies g(i)=0 \,\bigg\}$$

The vector space corresponding to the affine space $\mathcal{A}_S$ is

$$V_S:= \bigg\{\, g: P\to \mathbb{R} \,\,\,\bigg|\,\,\,\sum_{p\in P} g(i)=0\mbox{   and   }i\notin S \implies g(i)=0 \,\bigg\}$$

and each $\mathcal{A}_S$ is spanned by the simplex

$$\Sigma_S:=\big\{\, g\in\mathcal{A}_{S} \,\,\,\big|\,\,\,g(i)\geq 0 \mbox{   for all   } i\in P \,\big\}.$$

The whole space  $C(\mathcal{S})$ is the disjoined union of all the interiors (within $\mathcal{A}_S$) of the simplices $\Sigma_S$ for $S\in \mathcal{S}$. If $S\in \mathcal{S}$ and $T\subset S$ then $\mathcal{A}_T$ is an affine subspace of $\mathcal{A}_S$. Similarly, we also have $\Sigma_T \subset \Sigma_S$ in this case.

Each point $i\in P$ corresponds to a particular element $\delta_i\in C(\mathcal{S})$ defined by $\delta_i(j)=1$ for $j=i$ and $\delta_i(j)=0$ otherwise. We have $\mathcal{A}_{\{p\}}=\Sigma_{\{i\}}=\{\delta_i\}$. The main property that makes simplicial complexes useful for physical modeling is the following easy-to-prove

Theorem: Let $\mathcal{S}$ be a simplicial complex with point set $P$ and let  $f: P \to V$ be a map into any vector space $V$. Then there is a unique map

$$\hat{f}:C(\mathcal{S})\to V$$

whose restriction to each simplex $\Sigma_S$ is affine and which extends $f$ in the sense that for all $i\in P$ we have

$$\hat{f}(\delta_i)=f(i).$$

In particular, if we have a two-dimensional simplicial complex and are given a position in $\mathbb{R}^3$ 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.