Simplex tree

In topological data analysis, a simplex tree is a type of trie used to represent efficiently any general simplicial complex. Through its nodes, this data structure notably explicitely represents all the simplices. Its flexible structure allows implementation of many basic operations useful to computing persistent homology. This data structure was invented by Jean-Daniel Boissonnat and Clément Maria in 2014, in the article The Simplex Tree: An Efficient Data Structure for General Simplicial Complexes. This data structure offers efficient operations on sparse simplicial complexes. For dense or maximal simplices, Skeleton-Blocker representations or Toplex Map representations are used.

Definitions

Many researchers in topological data analysis consider the simplex

Heuristic definition

Consider any simplicial complex is a set composed of points (0 dimensions), line segments (1 dimension), triangles (2 dimensions), and their n-dimensional counterparts, called n-simplexes within a topological space. By the mathematical properties of simplexes, any n-simplex is composed of multiple $(n-1)$-simplexes. Thus, lines are composed of points, triangles of lines, tetrahedrons of triangle. Notice each higher level adds 1 vertex to the vertices of the n-simplex. The data structure is simplex-based, therefore, it should represent all simplexes uniquely by the points defining the simplex. A simple way to acheive this is to define each simplex by its points in sorted order.

Let $\mathrm {K}$ be a simplicial complex of dimension k, $V$ its vertex set, where vertices are labeled from 1 to $\left\vert V\right\vert$ and ordered accordingly. Now, construct a dictionnary size $\left\vert V\right\vert$ containing all vertex labels in order. This represents the 0-dimensional simplexes. Then, for the path to the initial dictionary of each entry in the initial dictionary, add as a child dictionnary all vertices fully-connected to the current set of vertices, all of which having a label greater than $l$. Represent this step on k levels. Clearly, considering the first dictionnary as depth 0, any entry at depth $\tau$ of any dictionary in this data structure uniquely represents a $\tau$-simplex within $\mathrm {K}$.

Applications

Simplex tree are efficient in sparse simplicial complexes. For this purpose, many persistent homology algorithms focusing on high-dimensional real data (often sparse) use simplex trees within these algorithms.