In topological data analysis, a simplex tree is a type of trie used to efficiently represent any general simplicial complex. Through its nodes, this data structure notably represents all the simplices. Its flexible structure allows the 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 tree to be the most compact simplex-based data structure for simplicial complexes, and a data structure allowing an intuitive understanding of simplicial complexes due to integrated usage of their mathematical properties.
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 ) {\displaystyle (n-1)} -simplexes. Thus, lines are composed of points, triangles of lines, and tetrahedrons of triangles. 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 achieve this is to define each simplex by its points in sorted order. Let K {\displaystyle \mathrm {K} } be a simplicial complex of dimension k, V {\displaystyle V} its vertex set, where vertices are labeled from 1 to | V | {\displaystyle \left\vert V\right\vert } and ordered accordingly. Now, construct a dictionary size | V | {\displaystyle \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 dictionary all vertices fully-connected to the current set of vertices, all of which have a label greater than l {\displaystyle l} . Represent this step on k levels. Clearly, considering the first dictionary as depth 0, any entry at depth τ {\displaystyle \tau } of any dictionary in this data structure uniquely represents a τ {\displaystyle \tau } -simplex within K {\displaystyle \mathrm {K} } . For completeness, the point to the initial dictionary is considered the representation of the empty simplex. For the practicality of the operations, labels that are repeated on the same level are linked together, forming a looped linked list. Finally, child dictionaries also have pointers to their parent dictionary, for fast ancestor access.
Constructive definition Let K {\displaystyle \mathrm {K} } be a simplicial complex of dimension k. We begin by decomposing the simplicial complex into mutually exclusive simplexes. This can be achieved in a greedy way by iteratively removing from the simplicial complex the highest order simplexes until the simplicial complex is empty. We then need to label each vertex from 1 to | V | {\displaystyle \left\vert V\right\vert } and associate each simplex with its corresponding "word", that is the ordered list of its vertices by label. Ordering the labels ensures no repetition in the simplex tree, as there is only one way to describe a simplex. We start with a null root, representing the null simplex. Then, we iterate through all simplexes, and through each label of each simplex word. If the label is available as a child to the current root, make that child the temporary root of the insertion process, otherwise, create a new node for the child, make it the new temporary root, and continue with the rest of the word. During this process, k dictionaries are maintained with all the labels and insert the address of the node for the corresponding label. If an address is already at that space in the dictionary, a pointer is created from the old node to the new node. Once the process is finished, all children of each node are entered into a dictionary, and all pointers are looped to make looped linked lists. A wide range of dictionaries could be applied here, like hash tables, but some operations assume the possibility of an ordered traversal of the entries, leading most of the implementations to use red-black trees are dictionaries.
… excerpt ends here. Continue reading the full article.
