<p>First you can read the CGAL documentation that can help you to understand <a href="https://doc.cgal.org/latest/Combinatorial_map/" rel="nofollow noreferrer">combinatorial</a> and <a href="https://doc.cgal.org/latest/Generalized_map/" rel="nofollow noreferrer">generalized</a> maps, since it provide several examples. You can also read the book <a href="https://www.crcpress.com/Combinatorial-Maps-Efficient-Data-Structures-for-Computer-Graphics-and/Damiand-Lienhardt/p/book/9781482206524" rel="nofollow noreferrer">"Combinatorial Maps: Efficient Data Structures for Computer Graphics and Image Processing"</a>.</p>

<p>Now some answers:</p>

<p>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...</p>

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

<p>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 <a href="https://doc.cgal.org/latest/Combinatorial_map/index.html#fig__fig_cmap_non_valid" rel="nofollow noreferrer">following example</a>).</p>

<p>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.</p>

<p>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. <a href="https://doc.cgal.org/latest/Combinatorial_map/index.html#sseccombimapvalidity" rel="nofollow noreferrer">this section</a>).</p>

<p>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 <a href="https://doc.cgal.org/latest/Generalized_map/index.html#fig__fig_gmap_sew_non_orientable" rel="nofollow noreferrer">example here</a>).</p>

<p>Hope this helps, and welcome into the fabulous world of combinatorial maps !</p>

CC BY-SA 4.0
2020-01-06T18:02:37.513Z
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.
Will
CC BY-SA 4.0
2020-01-07T09:18:33.590Z
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.
gdamiand
CC BY-SA 4.0
2020-01-06T16:13:02.020Z
2020-01-06T16:13:02.020Z
gdamiand
<p>I am looking for a data structure to encode an <span class="math-container">$n$</span>-dimensional simplicial complex with an embedding in <span class="math-container">$\mathbb{R}^{n+1}$</span>. I am aware of <a href="https://en.wikipedia.org/wiki/Combinatorial_map" rel="nofollow noreferrer">combinatorial maps</a>, which generalize rotation systems of planar graphs, and <a href="https://en.wikipedia.org/wiki/Generalized_map" rel="nofollow noreferrer">generalized maps</a> which further generalize combinatorial maps to allow for non-orientability.</p>

<p>From Wikipedia, a combinatorial map is defined as an <span class="math-container">$(n+1)$</span>-tuple <span class="math-container">$(D, \beta_1,\dots,\beta_n)$</span> such that:</p>

<p>1) <span class="math-container">$D$</span> is a finite set of darts,</p>

<p>2) <span class="math-container">$\beta_1$</span> is a permutation on <span class="math-container">$D$</span>,</p>

<p>3) <span class="math-container">$\beta_2, \dots, \beta_n$</span> are involutions on <span class="math-container">$D$</span>,</p>

<p>4) <span class="math-container">$\beta_i \circ \beta_j$</span> is an involution if <span class="math-container">$i + 2 \leq j$</span>.</p>

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

<p>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."</p>

<p>Here are my questions about this data structure:</p>

<p>1) Are my interpretations of conditions 1-3 correct? </p>

<p>2) What is the geometric interpretation of condition 4? </p>

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

<p>4) What is a quasi-manifold subdivision?</p>

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

<ds.data-structures><computational-geometry><topology>
Data structures for embedded simplicial complexes
Will
# Data structures for embedded simplicial complexes

(Asked by: username_0 on 2020-01-03)

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](https://en.wikipedia.org/wiki/Combinatorial_map), which generalize rotation systems of planar graphs, and [generalized maps](https://en.wikipedia.org/wiki/Generalized_map) 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?

**Tags:** ds.data-structures, computational-geometry, topology

---

## 1 answers

### Answer by username_1 on 2020-01-06. Score: 2 | Accepted answer

First you can read the CGAL documentation that can help you to understand [combinatorial](https://doc.cgal.org/latest/Combinatorial_map/) and [generalized](https://doc.cgal.org/latest/Generalized_map/) maps, since it provide several examples. You can also read the book ["Combinatorial Maps: Efficient Data Structures for Computer Graphics and Image Processing"](https://www.crcpress.com/Combinatorial-Maps-Efficient-Data-Structures-for-Computer-Graphics-and/Damiand-Lienhardt/p/book/9781482206524).

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](https://doc.cgal.org/latest/Combinatorial_map/index.html#fig__fig_cmap_non_valid)).

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](https://doc.cgal.org/latest/Combinatorial_map/index.html#sseccombimapvalidity)).

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](https://doc.cgal.org/latest/Generalized_map/index.html#fig__fig_gmap_sew_non_orientable)).

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

> **Comments:**
> **username_0**: 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.  
> **username_1**: 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.  

---

