Monthly Archives: March 2014

Simplicial complexes are discretizations of real-life shapes

yellow-ring-6triangles In this post we answer the following questions of topological data analysis:

  • what are simplicial complexes and what are they not?
  • how can a shape be represented by a simplicial complex?
  • why are simplicial complexes easy for representing shapes?

Simplices are building blocks of complexes

A simplicial complex is a high-dimensional generalization of a graph. That is why simplicial complexes are sometimes called hypergraphs. The building blocks of a simplicial complex are vertices, edges, triangles and higher-dimensional simplices like tetrahedra in \(\mathbb{R}^3\).

The standard k-dimensional simplex is the subset of points in the \(k\)-dimensional space:
\(\Delta^k=\{(x_1,\dots,x_k)\in\mathbb{R}^k \; :\; 0\leq x_i\leq 1,\; \sum\limits_{i=1}^k x_i=1\}\).

We may say that the simplex \(\Delta^k\) is spanned by its \(k+1\) vertices marked by (say) \(0,1,\dots,k\). Any subset of \(l\) vertices spans an \(l\)-dimensional face (or a subsimplex) of \(\Delta^k\).

Many geometrically different shapes are homeomorphic (topologically equivalent) to the same simplex \(\Delta^k\subset\mathbb{R}^k\). For instance, the 2-dimensional disk \(\{(x,y)\in\mathbb{R}^2\; :\; x^2+y^2\leq 1\}\) is homeomorphic to the standard triangle \(\Delta^2\). Then the combinatorial structure of \(\Delta^2\) induces a similar structure on the disk, namely 3 vertices, 3 edges and one 2-dimensional face.


A triangulation is a structure on a shape

A triangulation of (or the structure of a simplicial complex on) a shape is

  • a splitting into finitely many pieces homeomorphic to simplices in such a way that
  • the intersection of any two simplices in the triangulation is their common face.

A shape is called triangulable if it has a triangulation satisfying the above conditions. A simplicial complex may contain simplices of different dimensions as shown in the sun glasses below. The dimension of a simplicial complex is the maximum dimension of its simplices.

sun-glasses-encodingRepresenting a shape as a simplicial complex allows us to introduce later topological invariants of shapes. For instance, the Euler characteristic of a shape is expressed via the number of \(l\)-dimensional simplices in a trianglation for different values of \(l\).

Encoding simplicial complexes

The condition on intersection of simplices in dimension 1 means that any two edges can meet only at a single common vertex. Hence a 1-dimensional simplicial complex can not have loops or double edges with the same endpoints. This condition seems too restrictive for graphs, but is essential for higher dimensions as explained below.

Any simplicial complex with vertices marked by (say) \(0,1,\dots,n\) can be encoded by a list of maximum simplices that are not contained in larger simplices. Any maximum simplex spanned by \((k+1)\) vertices \(i_0,\dots,i_k\) is encoded by the unordered \((k+1)\)-tuple \((i_0,\dots,i_k)\). The sun glasses with 8 vertices above are encoded by the list (012),(345),(05),(14),(26),(37).

Triangulations of 2-dimensional shapes

To encode a shape, first we should triangulate it. Let us split a round ring into 4 triangles with vertices 0,1,2,3 below. The corresponding list of triples is (012),(013),(023),(123).ring-4trianglesWe may notice that the same list of triples encodes the standard tetrahedron \(\Delta^3\) with four 2-dimensional faces. To avoid this confusion, the definition of a simplicial complex requires that any two simplices should meet along their common face. So the splitting into 4 curved triangles above is not a simplicial complex.

If our code contains triples (123) and (013), we should know that the corresponding triangles share the common edge (13) as in the tetrahedron \(\Delta^3\), not only the endpoints 1 and 3 as in the round ring. A minimum triangulation of a round ring is at the beginning of this post.

In conclusion, we highlight answers to the questions posed at the beginning of the post:

  • a simplicial complexes is glued from standard simplices along their common faces,
  • to represent a shape, we triangulate it into pieces homeomorphic to simplices,
  • simplicial complexes can be easily encoded in a computer memory, hence
    they provide a convenient representation of a shape for further analysis.

Exercises on triangulations of shapes

  • Q1. Encode the figure-eight shape below by a simplicial complex.
    Hint. Each of 3 boundary contours should have at least 3 vertices.
  • Q2. Find a minimum triangulation of the 2-dimensional torus below.
    Hint. A minimum triangulation of the torus has at least 7 vertices.

figure-eight-shape                   green-torus2D

You could write a brief solution or feedback in your comment: reply.