G-maps mini-course

1. Darts rather than vertices

A classic mesh stores vertices, edges and faces. A generalized map (G-map) stores something else: darts. Each face is cut into its sides, then each side into two halves, one at each end: each half is a dart.

A square has 4 sides, so 8 darts. The cube has 6 square faces: its G-map has 6 × 8 = 48 darts. They are the short segments in the figure below; the dot marks the end, that is the vertex, the dart belongs to.

2. Three links, α0, α1 and α2

Darts are linked in pairs, and each link changes exactly one thing. α0 links the two darts of a side: same face, same edge, other vertex. α1 links, at a vertex, the darts of two consecutive sides: same face, same vertex, other edge. α2 links the darts of two neighbouring faces: same edge, same vertex, other face.

Each αi is an involution: applying it twice gives the starting dart back, αi(αi(d)) = d. A dart without an α2 partner is linked to itself: it is "2-free", and it marks a boundary of the surface. The cube is closed: none of its darts is free.

3. A consistency constraint

Links are not placed at random. Take an edge of face A, from vertex v to vertex w, and a dart d of A at v; its neighbour α0(d) is at w. If α2 sews d to the dart d' of face B, the edge must be sewn in one piece: the other end too, α2(α0(d)) = α0(d'). Since d' = α2(d), this reads α2 α0 = α0 α2: going to the end of the edge then changing face, or changing face then going to the end, leads to the same dart.

The involution follows. Replacing α2 α0 with α0 α2 in the middle, α0 α2 α0 α2 = α0 α0 α2 α2, and each αi applied twice cancels out: the cycle comes back to the starting dart. Conversely, if α0 α2 is an involution, it is its own inverse, α2 α0: the two statements are equivalent. What they forbid is an edge sewn to B at one end and to another face, or to nothing, at the other. A boundary is still allowed, as long as it is free at both ends.

The rule only holds for α0 and α2, which are not consecutive. α0 α1 moves one vertex round a face: on a square it takes four steps, not two, to come back. α1 α2 turns round a vertex: three steps on the cube.

The project's library checks these constraints on every dart; a map that breaks them is not a G-map.

4. Cells are orbits

Vertices, edges and faces are not stored: they are found by following some of the links. The ⟨α1, α2⟩ orbit of a dart, every dart reached using only α1 and α2, is a vertex. The ⟨α0, α2⟩ orbit is an edge, the ⟨α0, α1⟩ orbit a face, and ⟨α0, α1, α2⟩ the whole connected component.

In the cube, a vertex gathers 6 darts (3 faces meet there, 2 darts each), an edge 4, a face 8. Pick a dart in the figure and show its orbits.

5. Counting to understand the shape

Counting orbits gives the Euler characteristic: χ = V − E + F. For the cube, 8 − 12 + 6 = 2, as for any surface without holes; a torus gives 0. With the number of components and boundaries, it gives the genus, the number of "holes".

G-maps also represent non-orientable surfaces. A surface is orientable when its darts can be coloured in two colours so that every link joins two different colours. On the Moebius strip it cannot be done: going once round the strip comes back to the starting colour.

6. Why it is useful

Each dart knows its direct neighbours: many topological computations are local, dart by dart, hence parallel. G-maps extend to dimension 3 (with α3, for volumes) and beyond without changing their principle.

In my thesis, this formalism was used to analyse the topology of meshes of the cerebral vascular tree, from local information computed in parallel.