This site contains: mathematics courses and book; covers: image analysis, data analysis, and discrete modelling; provides: image analysis software. Created and run by Peter Saveliev.
Simplicial complex
From Intelligent Perception
Just like cubical complexes a simplicial complex is a special kind of cell complex. But instead of cubes/squares, it's made of triangles, tetrahedra, ..., simplices:
Since they have fewer edge, simplices are indeed simpler then anything else, even cubes:
You can also compare the boundary operators.
Just like cubical complexes come from digital imaging, simplicial complexes sometimes come from a related source: scanning. A laser scanner send a beam at the objects in a sequence of pulses. Each redout produces a point in the 3d space:
Eventually scanning produces a "point cloud" which later is turned into a complex by adding edges, then faces, etc. How?
A simplistic approach is to choose a threshold $r>0$ and then
- add an edge between any two points if they are within $r$ from each other,
- add a face spanning three points if the diameter of the triangle is less then $r$,
etc.
More sophisticated approaches are: Vietoris-Rips complex, Čech complex, Delaunay triangulation, etc.
Another source of point clouds is data.
Let's compare simplicial complexes to others.
Cell complexes:
Cubical complexes:
Simplicial complexes:
The simplest example of $n$-simplex is the polygon in ${\bf R}^n$ with $n+1$ vertices at $$(0,0,0,0,...,0), (1,0,0,0,...,0), (0,1,0,0,...,0), \ldots , (0,0,0,0,...0,1,0), (0,0,0,0,...,0,1),$$ illustrated here in 3D:
More precisely, an $n$-simplex is defined as the convex hull of $n+1$ points $$v_0 v_1 \ldots v_n = {\rm conv}\{v_0, v_1, \ldots, v_n \}$$ in general position, which means:
We need the last restriction because, for example, the convex hull of three points isn't always a triangle (e.g., ${\rm conv}\{(0,0),(1,0),(2,0)\}$).
Theorem. The $n$-simplex is homeomorphic to the $n$-ball ${\bf B}^n$.
There is however an additional combinatorial structure; a simplex has faces.
Example. Suppose $a$ is a $1$-simplex $$a = v_0v_1.$$ Then its faces are $v_0$ and $v_1$. They can be easily described algebraically. An arbitrary point in $a$ is a convex combination of $v_0$ and $v_1$: $$a_0v_0 + a_1v_1 {\rm \hspace{3pt} with \hspace{3pt}} a_0 + a_1 = 1.$$
What about $v_0$ and $v_1$? They are convex combinations too but of a special kind: $$v_0 = a_0v_0 + a_1v_1 {\rm \hspace{3pt} with \hspace{3pt}} a_0 = 1, a_1 = 0,$$ $$v_1 = a_0v_0 + a_1v_1 {\rm \hspace{3pt} with \hspace{3pt}} a_0 = 0, a_1 = 1.$$
For notation we write
- $\sigma < \tau$ if $\sigma$ is a face of $\tau$.
Similar ideas apply to higher dimensions.
Example. Suppose $\tau$ is a $2$-simplex $$\tau = v_0v_1v_2.$$ An arbitrary point in $\tau$ is a convex combination of $v_0,v_1,v_2$: $$a_0v_0 + a_1v_1 + a_2v_2 {\rm \hspace{3pt} with \hspace{3pt}} a_0 + a_1 + a_2 = 1.$$
To find all $1$-faces set one of these coefficient equal to $0$: $$a = a_0v_0 + a_1v_1 + a_2v_2 {\rm \hspace{3pt} with \hspace{3pt}} a_0 + a_1 + a_2 = 1 {\rm \hspace{3pt} and \hspace{3pt}} a_2 = 0,$$ $$b = a_0v_0 + a_1v_1 + a_2v_2 {\rm \hspace{3pt} with \hspace{3pt}} a_0 + a_1 + a_2 = 1 {\rm \hspace{3pt} and \hspace{3pt}} a_1 = 0,$$ $$c = a_0v_0 + a_1v_1 + a_2v_2 {\rm \hspace{3pt} with \hspace{3pt}} a_0 + a_1 + a_2 = 1 {\rm \hspace{3pt} and \hspace{3pt}} a_0 = 0.$$ So, $$a,b,c < \tau.$$
To find all $0$-faces set two of these coefficient equal to $0$: $$v_0 = 1 \cdot v_0 + 0 \cdot v_1 + 0 \cdot v_2, {\rm \hspace{3pt} etc}.$$
Definition. Given $\tau$ an $n$-simplex $$a = v_0v_1 \ldots v_n,$$ then the convex hull $\sigma$ of any $k+1, k<n$, vertices of $\tau$ is called a $k$-face of $\tau$.
Observe that by face we mean a proper face.
Now we would like to define simplicial complexes as cell complexes whose cells are homeomorphic to simplices... It wouldn't make sense though to leave it this way because cells of any cell complex are homeomorphic to balls homeomorphic to simplices. We want the faces of simplices to be nicely attached to each other.
The problem with the second example here is that $\tau$ is glued to two faces of $\sigma$.
Definition. A cell complex $K$ is a simplicial complex if
- (1) each of its cells has the structure of a simplex, i.e., there is a homeomorphism to a geometric simplex;
- (2) the complex contains all faces of each simplex:
$$\tau \in K, \sigma < \tau \Rightarrow \sigma \in K,$$
- (3) two simplices can only share a single face:
$$\tau, \sigma \in K \Rightarrow \tau \cap \sigma < \tau.$$
Note: The last condition implies that a simplex can't be attached to itself (remember how the circle is created?).
Any cell complex can be turned into a simplicial complex. How? By subdivision, i.e., cutting the cells into smaller cells - triangles - until the above conditions are satisfied.
Sidenote: the procedure is reminiscent of the subdivision of intervals in the definition of the Riemann integral via Riemann sums.
Example. The simplest cell complex representation of the circle -- one $0$-cell and one $1$-cell -- is not a simplicial complex.
We add an extra vertex that cuts $a$ in two, but this still isn't a simplicial complex since $c$ and $d$ share two faces. For that we need another subdivision:
Representation of a cell complex or a topological space as a simplicial complex is called triangulation.
For a given space, its triangulation isn't unique. In particular, any further subdivision of the above simplicial complex will be a triangulation.
Example. The familiar representation of the cylinder isn't a triangulation simply because the $2$-cell is a square not triangle.
Cutting it in half diagonally doesn't make it a triangulation because a new $2$-cell $\alpha$ is glued to itself. Adding more edges does the job.
Exercise. Find a triangulation of the torus. Solution: 
Exercise. Find a triangulation for each of the main surfaces.
Once all the cells are simplices, the triangulation can be found via the so-called barycentric subdivision: every simplex (of any dimensions) gets a new vertex inside and all possible faces are added as well.
For the $3$-simplex above, one:
- keeps the $4$ original vertices,
- adds $6$ new vertices on each edge,
- adds $4$ new vertices on each face, and
- adds $1$ new vertex inside.
Then one adds many new edges and faces.
Exercise. Find a triangulation for the cube.
Simplicial complexes also come in the form of abstract simplicial complexes. In fact, every open cover of a topological space will produce one via the nerve of cover construction.
One-dimensional simplicial complexes are called graphs.
See also Simplicial map.
