# Distributed Combinatorial Maps for Parallel Mesh Processing
## Preliminary Notions
### \(n\)D Combinatorial Map
** One important property of \(n\)-maps, which guarantees the topological validity of the represented objects, links all pairs of \(\beta_{i}\) and \(\beta_{j}\) mappings, for \(|i-j|\geq 2\): \(\beta_{i}\circ\beta_{j}\) must be an involution. For example, when two volumes are glued together, they share an entire face. In other words, the two parts of the shared face must have the same number of darts (and thus the same number of vertices and edges), which is verified by ensuring that \(\beta_{1}\circ\beta_{3}\) is an involution. This property must be satisfied for each dart of the \(n\)-map. As a consequence, operations that modify an \(n\)-map must ensure that the resulting \(n\)-map still satisfies this property. **Free darts. ** An \(n\)-map allows us to represent an \(n\)D object with _boundaries_. In such an object, some \((n-1)\)-cells belong to the _border_ of the object, i.e., there is only one \(n\)-cell containing it. All the darts that belong to these \((n-1)\)-cells do not have darts linked with them by \(\beta_{n}\). These darts are said **n-free;** and are all linked by \(\beta_{n}\) with a special value called \(\varnothing\). **Cells in \(n\)-maps. ** Cells are represented implicitly in an \(n\)-map by the darts and the mappings. Each \(i\)-cell, \(1\leq i\leq n\), is defined by the set of darts that can be reached from one of its darts by using all \(\beta_{j}\), \(\forall j\
eq i\). Things are a little bit different for \(0\)-cells (vertices): each \(0\)-cell is defined by the set of darts that can be reached from one of its darts by using all combinations of two different \(\beta\). Thanks to this definition of cells and the definition of adjacency and incidence relations, we are able to retrieve all the topological relations in a given \(n\)-map. **Illustration of the relations. ** Let us take a closer look at some parts of Figure 1. Figure 2a shows the part of the \(3\)-map that represents \(V_{0}\). In this example, \(\beta_{0}(1)=3\), \(\beta_{1}(1)=2\) and \(\beta_{2}(1)=4\). Since \(\beta_{2}\) is an involution, \(\beta_{2}(4)=1\). Figure 2b shows the part of the \(3\)-map around the face between \(V_{0}\) and \(V_{1}\), where \(\beta_{3}(4)=8\). Since \(\beta_{3}\) is an involution, \(\beta_{3}(8)=4\). All the darts of the \(3\)-map shown in Figure 1b are \(3\)-free, except the darts that belong to the four faces around the central edge. For example, darts \(1\), \(2\) and \(3\) are \(3\)-free, while dart \(4\) is not \(3\)-free. We can observe the composition property of \(3\)-maps on Figure 2b. We can for example verify that \(\beta_{1}\circ\beta_{3}(4)=9\) and \(\beta_{1}\circ\beta_{3}(9)=4\). **\(i\)-attributes. ** An \(n\)-map only describes the combinatorial part of an \(n\)D object, i.e., its subdivision in cells, and all the adjacency and incidence relations between the cells. This is usually not enough in many applications where it is required to have additional information  
Figure 1. (**a**) A \(3\)D mesh composed of \(4\) cubes, \(V_{0}\), \(V_{1}\), \(V_{2}\), \(V_{3}\), two by two adjacent; (**b**) The corresponding \(3\)-map having \(96\) darts (\(24\) for each cube) where some darts are numbered. For example, we need the geometry of the object to visualize it. This can be done by associating a point of \(\mathbb{R}^{3}\) to each vertex of the \(n\)-map. More generally, it is possible to associate any information to any \(i\)-cell in an \(n\)-map by using the notion of **i-attribute** (for example a position to each vertex, a color to each face, or an id to some edges).