# Distributed Combinatorial Maps for Parallel Mesh Processing
## 1 Introduction  
_Meshes_ are an essential concept for representing objects in computers. They are used for example in Computer-Aided Design, in geometric modeling, or in physical simulations with the Finite Element Method. Many data structures have been defined to describe meshes. They can be separated into two main categories: (1) constructive solid geometry (_CSG_), where objects are described as collections of basic primitives, combined together by Boolean operations; (2) boundary representation models (_B-rep_), where the boundaries of objects are described by a description of the surface elements (vertices, edges, faces) connected together by boundary relations. B-rep models are usually more flexible than CSG ones and have richer operations. These advantages explain why B-rep models are very often used in applications that want to describe and modify objects. The objects handled are often _polygon meshes_, described only by their _surfaces_. Indeed, this type of description is enough in many applications, as for example in the main 3D computer graphics applications where we only want to visualize, analyze and modify the _shape_ of objects [1]. However, this type of model cannot be used in applications that need to represent both the exterior and the interior volumes of a 3D object [2]. This is the case for simulation applications, which require to represent the interior volumes of an object to associate material properties and perform computations for each internal element [3]. This is also the case in modeling applications of buildings that describe a building as an assembly of several 3D objects [4]. These applications require _volume meshes_ to represent and to handle both the exterior and the interior of 3D objects. Lastly, some applications require to describe objects in higher dimension. We can cite for example some problems in visibility and in geometric optimization that involve generalized Voronoi diagrams in any dimension [5], or some work that would like to represent 3D objects added with some feature dimension spaces, suchas for example the project of urban modeling in higher dimensions [6], or the reconstruction of 5D respiratory motion models [7]. These different needs show the interest of having a generic data structure that is able to describe meshes in any dimension. Many different data structures were defined to represent polygon meshes. A first model defined was the _winged-edge_ data structure [8], followed by many solutions based on a similar idea, each provides different advantages, drawbacks and power of representation. We can cite the _half-edges_ or _DCEL_[9; 10; 11], _quad-edges_[12], _radial-edges_[13], _corner table_[14], etc. Other works in the field of combinatorics defined solutions in order to represent planar graphs embedded in the plane, or polyhedral surfaces, such as [15; 16; 17; 18]. However, all these data structures are only able to describe surface meshes: it is not possible to describe subdivided 3D objects made of several combinations of atomic elements, nor to describe objects in higher dimension. Few data structures were defined to represent volumetric meshes, like for example _facet-edge_[19], _handle-face_[20], OpenVolumeMesh [21] or _AHF_[22]. However, these solutions are not able to describe \(n\)D meshes. The choice of a data structure becomes very limited when we want to represent \(n\)D objects. Several graph-based solutions were proposed. For example, in the incidence graph [23; 24], each cell is represented as a node, and an arc exists between each pair of nodes corresponding to two incident cells whose dimensions differ by one. This data structure is simple, but has several drawbacks. First, it cannot represent multi-incidence relations, which often occur in real applications. Second, the incidence graph is not ordered, e.g., it does not allow us to iterate through all the vertices of a face in a given order, which leads to complex and inefficient operations. In order to solve these drawbacks, _combinatorial maps_[25; 26] were defined.