I am looking for a data structure to encode an $n$-dimensional simplicial complex with an embedding in $\mathbb{R}^{n+1}$. I am aware of combinatorial maps, which generalize rotation systems of planar graphs, and generalized maps which further generalize combinatorial maps to allow for non-orientability.

From Wikipedia, a combinatorial map is defined as an $(n+1)$-tuple $(D, \beta_1,\dots,\beta_n)$ such that:

1) $D$ is a finite set of darts,

2) $\beta_1$ is a permutation on $D$,

3) $\beta_2, \dots, \beta_n$ are involutions on $D$,

4) $\beta_i \circ \beta_j$ is an involution if $i + 2 \leq j$.

Here's my understanding of the definition. The set $D$ should contain $n+1$ darts for each $n$-simplex as this is the natural generalization of a half-edge in a planar rotation system. The permutation $\beta_1$ describes the cyclic order in which the $n$-simplices are incident to a common $(n-1)$-simplex. The involutions $\beta_2,\dots,\beta_n$ allow you to move from one $(n-1)$-simplex to another along a common $n$-simplex, which generalizes the one involution needed to define the half-edges in a planar rotation system.

I don't understand what condition 4 is used for, however Wikipedia states that it is included to "fix constraints which guarantee the topological validity of the represented object: a combinatorial map represents a quasi-manifold subdivision."

Here are my questions about this data structure:

1) Are my interpretations of conditions 1-3 correct?

2) What is the geometric interpretation of condition 4?

3) Can a combinatorial map be used to encode any orientable embedded simplicial complex, or just quasi-manifold subdivisions?

4) What is a quasi-manifold subdivision?

5) Why does the definition of a combinatorial map fail for non-orientable complexes?


1 Answer 1


First you can read the CGAL documentation that can help you to understand combinatorial and generalized maps, since it provide several examples. You can also read the book "Combinatorial Maps: Efficient Data Structures for Computer Graphics and Image Processing".

Now some answers:

1) I don't think. In a combinatorial map, in 2D, a triangle is described by 3 darts. In 3D, a tetrahedron is described by 4 triangles, thus 12 darts. Etc...

Given a dart $d$, each permutation, except $\beta_n$, stay in the same n-simplex. A dart corresponds to a n+1-tuple (vertex, edge, face, ..., n-simplex), and each $\beta_i$ (except $\beta_1$) can be seen as a switch for the $i^{th}$ element of the tuple (each switch also switches vertices).

2) Condition 4 ensures that when two n-simplices are glued along one of their (n-1)-face, all the darts of the two (n-1)-faces are correctly identified two by two (cf. the following example).

3) Only quasi-manifold. For example in 3D, you cannot represent two tetrahedra that share only a common vertex, since this is not a quasi-manifold.

4) A dD quasi-manifold is an object obtained by taking some isolated d-cells, and allowing to glue d-cells along (d-1)-cells (cf. this section).

5) Let us consider one simple example in 2D. Take a square with four edges a,b,c,d. Now you can identify edges a and c to form either an orientable strip or a Mobius strip. Thus you need two different type of identification. This is not possible with combinatorial maps but this is possible with generalized maps since one edge in 2D is described by two darts, allowing to choose which pair of darts are identified (cf. the example here).

Hope this helps, and welcome into the fabulous world of combinatorial maps !

  • $\begingroup$ Thanks, this is a very helpful answer. I would like to modify the combinatorial map to work for a larger class of complexes by allowing more than two $d$-cells to be glued along a common $(d-1)$-cell. Can this be achieved by adding a new permutation to keep track of the order in which the cells were glued? Similar to the cyclic ordering of edges about a vertex in a rotation system for a planar embedding. $\endgroup$
    – Will
    Jan 6, 2020 at 18:02
  • $\begingroup$ This is doable, but not straightforward. See for example the paper "X-maps: An Efficient Model for Non-manifold Modeling" which use a similar idea, but only in 3D. When modifying the combinatorial map definition (either adding new permutations, or replacing involutions by permutations), the key point is to show that cells are still defined correctly as set of darts obtained by some specific orbits. $\endgroup$
    – gdamiand
    Jan 7, 2020 at 9:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.