Data structures for embedded simplicial complexes

Question

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?

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 !