# Distributed Combinatorial Maps for Parallel Mesh Processing
## Preliminary Notions  
### \(n\)D Combinatorial Map  
In this section, we introduce all the main notions around \(n\)D combinatorial maps, intuitively based and illustrated on 3D examples. Interested readers can find all the definitions in [25; 26], in any dimension and with several operations. An \(n\)_D combinatorial map_ (also called \(n\)-map) is a topological data structure for representing an \(n\)D oriented object subdivided in _cells_. For example, in 3D we have: the _volumes_ that subdivide the interior of 3D objects, which are connected subsets of \(\mathbb{R}^{3}\); the _faces_ that separate adjacent volumes, which are subsets of planes; the _edges_ that separate adjacent faces, which are segments; and the _vertices_ that separate adjacent edges. We speak about _i-cells_ for cells of dimension \(i\): vertices are \(0\)_-cells_, edges are \(1\)-_cells_, faces are \(2\)-_cells_ and volumes are \(3\)-_cells_. An \(n\)D object has cells from dimension \(0\) to dimension \(n\). Two \(i\)-cells \(c_{1}\) and \(c_{2}\) are said to be _adjacent_ when they share a common \((i-1)\)-cell \(c\) in their boundary. In this case, \(c\) is said to be _incident_ to \(c_{1}\) and \(c_{2}\), and reciprocally. This incidence relation is closed by transitivity. To obtain an \(n\)-map from an \(n\)D object, cells are successively decomposed from dimension \(n\) to dimension \(1\). At the end, the basic elements resulting of this process are called _darts_ and are the unique atomic elements used in the \(n\)-map definition. Thus, each dart \(d\) corresponds to a sequence of incident cells \((c_{0},\ldots,c_{n})\) having dimensions from \(0\) to \(n\). Since the given \(n\)D object is oriented, only one out of two vertex incident to a given edge is used in sequences of incident cells that correspond to darts. Note that we could use _generalized maps_[25; 26] to represent non oriented objects. **Illustration of a \(3\)-map. ** Figure 0(a) shows an example of a 3D mesh composed of \(4\) volumes (\(V_{0}\), \(V_{1}\), \(V_{2}\), \(V_{3}\)), \(20\) faces, \(33\) edges and \(18\) vertices. Note that \(V_{0}\) and \(V_{1}\) are adjacent; \(V_{0}\) is incident to the red dashed face and to the green edge. To represent this 3D mesh with a \(3\)-map, each volume is decomposed; then each face of the volumes is decomposed; then each edge of the faces is decomposed. The darts can be seen in the \(3\)-map depicted in Figure 0(b) representing the 3D mesh of Figure 0(a). Each dart is depicted by an oriented segment. At the end, the \(3\)-map representing the 3D mesh has \(96\) darts (since each volume has \(6\) faces and each face has \(4\) edges, and thus, each volume is represented by \(24\) darts). **Adjacency relations. ** The adjacency relations of the \(n\)-map, which describe the topology of the \(n\)D object, are reported on the darts. \(n\) relations are defined for each dart \(d\):  
* \(\beta_{1}\) gives the dart after \(d\) that belongs to the same \(j\)-cells as the \(j\)-cells of \(d\), for all \(2\leq j\leq n\);
* \(\beta_{j}\), with \(2\leq i\leq n\), gives the dart different from \(d\) that belongs to the same \(j\)-cells as the \(j\)-cell of \(d\), for all \(j\
eq i\), \(1\leq j\leq n\). Intuitively, \(\beta_{i}\) allows us to swap the current \(i\)-cell while keeping the other \(j\)-cells unchanged, \(\forall j\
eq i\). \(\beta_{i}\), with \(2\leq i\leq n\) are _involutions_ (an involution is a bijection equal to its inverse). In other words, given a dart \(d\), we obtain \(d\) when applying \(\beta_{i}\) twice. \(\beta_{1}\) is not an involution but a _permutation_ (a permutation is a bijection having the same set \(D\) as domain and codomain). \(\beta_{0}\) denotes \(\beta_{1}^{-1}\). This mapping gives the dart before \(d\) that belongs to the same \(j\)-cells than \(d\), for all \(2\leq j\leq n\). At the end, an \(n\)-map is defined by the \((n+1)\)-tuple \((D,\beta_{1},\ldots,\beta_{n})\), i.e., a set \(D\) of darts plus the \(n\) mappings. **Composition property.