The Mangrove TDS Library
2.0
A C++ tool for the Fast Prototyping of Topological Data Structures

Here, we propose a brief analysis of the TriangleSegment (TS) data structure, initially proposed in [22] for representing simplicial complexes of dimension up to . In particular, we briefly propose its extension to a specific class of cell complexes, and its description as mangrove in our Mangrove TDS Library.
The TriangleSegment (TS) data structure is an explicit adjacencybased representation for any domain, including nonmanifolds (see the NonManifold Complexes Section) of dimension up to , discretized by simplicial and cell complexes, and necessarily embedded in the Euclidean 3D space. In particular, it exploits the radial sorting of cells around a nonmanifold edge, in order to reduce the amount of information to be encoded.
Given any cell complex (with ), the TS data structure encodes only vertices and top topological  and entities (cells that are not on the boundary of other cells), plus a subset of coboundary relations for each vertex, and a subset of adjacency relation for each top topological entity in .
In particular, for each vertex , it encodes partial coboundary relation , with , which associates with top edges, and one arbitrary top topological entity (representative cell) for each cluster in the star of . Recall that any cluster in the star of is a maximal subcomplex of , formed by top topological entities, which are incident at .
For each top edge , it encodes boundary relation , which associates with its two vertices.
For each top cell , it encodes:
In order to solve this drawback, the TS data structure also encodes partial coboundary , which is defined for each edge on the boundary of more than two cells. For each top cell in the star of , this relation consists of two top cells, which immediately precede and follow in radial order around edge . For example, edge in the following Figure is shared by triangles. For instance, we can define with respect to triangle (in yellow).
Partial topological relation allows for a compact encoding for adjacency relation for any top cell along one of its faces . In particular:
The graphbased representation of the TS data structure, which we call the TSgraph, is a partial mangrove. Let any cell complex (with ), then the TSgraph is formed by:
In particular, we can identify several spanning subgraphs of :
Encoding the TSgraph as mangrove requires to store also several Hasse diagrams (see the Ghost Topological Entities Section), one for each type of top cells in , for . Experimental results in [14],[12] show their storage cost does not depend on the number of top cells in , and their storage cost is basically not relevant.
The TS data structure is implemented in the mangrove_tds::Mangrove_TriangleSegment class, which is a subclass of the mangrove_tds::Mangrove_PartialMangrove class.
In particular, nodes of the TSgraph are stored in three arraybased collections of topological entities (see the Internal Encoding of Mangroves Section), one for vertices, one for cells (corresponding both to top and to nonmanifold, namely fake nodes), and one for maximal cells.
For a node , corresponding to a maximal cell, only indices of its vertices (of dimension ) are stored, as well as indices of cells (nonmanifold adjacency, corresponding to fake nodes) and cells (manifold adjacency), necessary for encoding adjacency relation along immediate faces of .
For a node , corresponding to a top edge, only indices of its vertices (of dimension ) are stored. On the contrary, for each fake node , corresponding to a nonmanifold edge , two indices of nodes, corresponding to top cells in , are encoded.
For a node corresponding to any vertex , only indices of top edges and representative cells of clusters, incident at , are stored.
The mangrove_tds::Mangrove_TriangleSegment class contains implementations of all topological queries, and editing operators. It is a templated class itself, built on the template Derived class. This latter is exploited in the context of the Curiously Recurring Template Pattern (as inherited by the mangrove_tds::Mangrove_Mangrove class) in order to implement the static polymorphism. In this way, we can reuse some parts and provide only member functions, specialized for the TS data structure.
template< class Derived > class Mangrove_TriangleSegment : public Mangrove_PartialMangrove< Derived > { public: /* Implementing topological queries and editing operators. */ ... };
In particular, in the mangrove_tds::Mangrove_TriangleSegment class, it is also possible to customize two aspects:
Specifically, these two aspects are fundamental for defining what top cells can be represented in the TS data structure. In order to support a wide range of possibilities, the current implementation of these aspects is parametric in the mangrove_tds::Mangrove_TriangleSegment class. These aspects must be managed in the templated Derived class, which is also a trait class. In the current implementation, we propose two specific traits:
class Mangrove_TriangleSegment_Simpl : public Mangrove_TriangleSegment< Mangrove_TriangleSegment_Simpl > { public: /* Topological queries and editing operators are inherited. */ ... /* Sorting vertices in increasing order */ ... /* Retrieving topological queries from supported Hasse diagrams. */ ... }; class Mangrove_TriangleSegment_Cell : public Mangrove_TriangleSegment< Mangrove_TriangleSegment_Cell > { public: /* Topological queries and editing operators are inherited. */ ... /* Sorting vertices in increasing order */ ... /* Retrieving topological queries from supported Hasse diagrams. */ ... };