Regular Surfaces and Regular Maps

Year: 2014 Authors: Faniry Razafindrazaka; Konrad Polthier

Core claim

Regular surfaces can be generated directly from regular map symmetry data and embedded in 3D without requiring an existing target realization.

Topics

regular maps, 3D visualization, hyperbolic surfaces, symmetry groups

Domains

group theory, topology, hyperbolic geometry, combinatorics, scientific visualization, computational geometry, interactive 3D modeling

Methods

coset enumeration, boundary identification, physically based relaxation, heuristic matching

Media

hyperbolic 4g-gons, edge graphs, transparent surface renderings

Paper text

The text below is the locally extracted OCR/Markdown version of the paper. Raw PDF files remain local and are not published here.

Page 1

Proceedings of Bridges 2014: Mathematics, Music, Art, Architecture, Culture

Regular Surfaces and Regular Maps

Faniry Razafindrazaka, Konrad Polthier

Freie Universität Berlin

{faniry.razafi,konrad.polthier}@fu-berlin.de

Abstract

A regular surface is a closed genus $g$ surface defined as the tubular neighbourhood of the edge graph of a regular map. A regular map is a family of disc type polygons glued together to form a 2-manifold which is flag transitive. The visualization of this highly symmetric surface is an intriguing and challenging problem. Unlike regular maps, regular surfaces can always be visualized as 3D embeddings. In this paper, we introduce an algorithm to visualize the regular surface formed around the tubular neighborhood of a regular map. Our algorithm takes as input the symmetry group of a regular map and outputs a 3D realization of its regular surface. This surface can be interactively modified and used as a target shape for other regular maps. As a result, we find new realizations of regular maps ranging from genus 9 to 85.

1 Introduction

A simple way to understand regular maps is to go back to the Platonic solids. They are the simplest examples of regular maps. They are built from regular polygons, glued at their edges with a uniform vertex figure. Additionally, they have the property of being flag transitive. In other words, moving a face or a vertex or an edge to another face or vertex or edge preserves all adjacency properties. Regular maps also exist for high genus surfaces. On the torus, they are checker-board, triangular and honeycomb like tilings. On surfaces of genus $g\ge 2$ , they are tilings of the hyperbolic space. They were first described by Coxeter [3] and later on enumerated by Conder [2] in the form of symmetry group.

Lately, a lot of efforts have been made to visualize high genus regular maps as a closed surface [10, 11, 6, 12, 8] but none of them successfully find an automatic procedure. Nevertheless, the work of van Wijk [6] is a huge source of inspiration and serves as guidance to this paper. To tackle the hard problem of visualizing regular maps, we approach it with a different point of view by generating regular surfaces which were implicitly introduced in [6].

A regular surface is a closed genus $g$ surface defined as the tubular neighbourhood of the edge graph of a regular map. Unlike regular maps, regular surfaces can always be embedded and we provide in this paper all the ingredients to achieve that. In [6], a regular surface is derived from an already embedded regular map (in Figure 1 are examples of them). We relaxed this constraint by generating directly the regular surface from the planar realization of the regular map.

Figure 1: Regular surfaces (transparent).

A regular map, following Conder [2], is denoted by $Rg.i\{p,q\}$ , where $g$ is the genus, $i$ is a constant and $\{p,q\}$ is the Schlafli symbol of the tiling. The dual map is represented by ${Rg.i}^{\prime }\{q,p\}$ . In this paper, if not explicitly stated, a regular map is denoted by $G_{pq}$ . The symmetry group is the same as in Conder [2] and is

Page 2

Razafindrazaka and Polthier

denoted by $\mathrm{Sym}(G_{pq})$ . We denote the regular surface of a regular map by $S_g$ . The mathematics required for understanding the paper can be found in the following books: for symmetry groups, we use [3]; for surface topology, we use [5]; and for hyperbolic geometry, we use [1, 9]. Nevertheless, we will try to make it as intuitive as possible.

Algorithm overview: the main steps of our algorithm are summarized as follows:

1. Take a regular map $G_{pq}$ , defined by its symmetry group $\mathrm{Sym}(G_{pq})$ , as input. The list of all regular maps from genus 2 to 302, in the form of symmetry group, is listed in [2].
2. Enumerate all element representatives of $\mathrm{Sym}(G_{pq})$ . This is done by using an advanced coset enumerator due to G. Havas and C. Ramsay [4] as explained in Section 2.
3. Make a hyperbolic realization of $\mathrm{Sym}(G_{pq})$ and find the correct identifications at the boundary. Planar realization of regular maps are well understood and can be found in [6, 7, 8]. Finding the correct identification at the boundary, on the other hand, have not yet been considered. We give a detailed description in Section 3.
4. Take the edge graph of the realization and identify the edges at the boundary. This makes the edge graph consistent but, unfortunately, induces a degenerate regular surface.
5. Define normals along the edge graph and apply a constrained physically based relaxation. Normals define the torsion of the regular surface $S_g$ and should be preserved. We use the physically based relaxation procedure in [7, 8] to get smoothness and symmetry.
6. (Optional) Introduce a group structure on $S_g$ and find matchings with other regular maps $G_{pq}^{\prime }$ using heuristics from [6].
7. (Optional) Visualize $G_{pq}^{\prime }$ .

Figure 2: Construction of a regular surface using the torus map $f$ for genus 1 regular maps (top), and using step 4 and 5 for higher genus regular maps (bottom).

Basically, steps 1 to 5 do what one would do to find the edge graph of some regular maps on the torus. These graphs are simply drawn on a flat rectangle and then mapped on the torus using the parametrization function of the torus (see Figure 2 up). This function does step 4 and 5 automatically and hence the associated tubular surface can be generated directly. For high genus regular maps, the flat rectangles are replaced by hyperbolic $4g$ -gons with pairwise identified edges. There is no known smooth map which identifies the edges of the $4g$ -gons to make the flat domain into a 3D surface. If such a map exists, then the problem of

Page 3

Regular Surfaces and Regular Maps

visualizing regular maps is solved. Step 4 does the mapping explicitly but only on the boundary edges (the triangles are ignored) and step 5 allows an interactive manipulation of the resulting graphs (see Figure 2 down).

Steps 3 to 5 are the most important steps of our algorithm. To understand them, we need to understand how symmetry groups act on a geometry and what are the possible geometric realizations of them. Step 4 is only combinatorial information, one can then use a good graph representation algorithm that will try to render the combinatorial graph in 3D with properly separated edges and with as much symmetry as possible.

In the following Section, we give an intuitive introduction to groups and representations, then in Section 3, we construct a topological representation of $G_{pq}$ . This is realized in the Poincaré model of hyperbolic space. In Section 4, we explain briefly our identification algorithm which is the first step to construct the medial axis of $S_g$ . In Section 5, we show how to construct the regular surface without any degeneration. And finally, in Section 6, we use our algorithm to generate space models of regular maps. We call it targetless realization of regular maps because, unlike van Wijk’s [6] cascade of mappings, our method does not need an actual 3D realization of the target regular map. We can then generate a wide variety of 3D embedded regular maps with as much symmetry as possible.

2 Groups and their Realizations

A group is a set with a well defined relation between its elements. A trivial example of a group is $\mathbb{Z}$ with the operation $+$ but, in general, a group can be anything: words, numbers, matrices, shapes, colors, abstract objects, etc. If a group can be realized as a geometrical shape, then we say that this shape is a geometric realization of the group and the group is the symmetry group of the shape. In Figure 3 are some examples of geometric realization of groups.

Figure 3: Examples of geometric realization of groups, from left to right: the Cubane with octahedral symmetry, the Rubik’s Cube group, a Wallpaper group and the Klein’s quartic (image source: Wikipedia).

A regular map is a group but at the same time it is a surface. The Klein’s quartic (Figure 3) is an example of regular map in its surface realization. The symmetry group of a regular map is denoted by $⟨R,S,T|\mathcal{R}(R,S,T)⟩$ , which is a set of words containing only $R,S$ and $T$ , with a set of relations $\mathcal{R}(R,S,T)$ between its elements. The symmetry group of the Klein quartic is given in Conder’s list [2] by

For example, $R^{-3}=I$ in this group which implies that $R^{-2}$ is the same as $R$ . Hence, these relations tell us exactly which element of the group corresponds to a given word. The software of Havas G. and Ramsay C. [4] gives this correspondence. It takes a word as input and returns an element of the group which represents this word.

Page 4

Razafindrazaka and Polthier

Our goal is now to find a geometrical realization of the group, first, as a triangular tiling in the hyperbolic space and second as a closed 3D surface.

3 Topological Representation of High Genus Regular Maps

Let $G_{pq}$ be a regular map of genus $\ge 2$ whose symmetry group is given by $\mathrm{Sym}(G_{pq})$ . This group can be realized as a triangular tiling in the hyperbolic plane, obtained from a triangle $M_0{N}_0{O}_0$ with corner angles $(\pi /p,\pi /q,\pi /2)$ by setting $R$ to be the rotation of angle $2\pi /p$ around $M_0$ , $S$ the rotation of angle $2\pi /q$ around $N_0$ and $T$ the reflection across the edge $M_0{N}_0$ (see Figure 4). We denote this tiling by $\mathrm{Tri}(G_{pq})$ . Each triangle of $\mathrm{Tri}(G_{pq})$ is a geometrical representation of an element of $\mathrm{Sym}(G_{pq})$ .

Figure 4: $\mathrm{Tri}(G_{pq})$ and $\mathrm{Line}(G_{pq})$ .

To make $\mathrm{Tri}(G_{pq})$ a topological closed surface, we need to make correct identifications for the triangles at the boundary. This is similar to the representation of a torus as a rectangle with identified opposite edges (see Figure 2). The correct identification at the boundary is obtained by finding the missing neighbour of each triangle of $\mathrm{Tri}(G_{pq})$ in $\mathrm{Sym}(G_{pq})$ using the relations of the group as in Section 2. For example, in Figure 5(a), triangle $T$ does not have a neighbour in $\mathrm{Tri}(G_{pq})$ which in this case should be $S$ . The relations of $\mathrm{Sym}(G_{pq})$ imply that $S$ and $S^{-1}{R}^3$ are the same. Since a triangle corresponding to $S^{-1}{R}^3$ exists in $\mathrm{Tri}(G_{pq})$ , we identify their $NO$ edges (blue lines). We proceed in the same way for all boundary triangles to obtain finally a planar realization of the regular map. Figure 5(b) is an example of a topological representation of the regular map R2.4{5,10} preserving flag transitivity.

(a)

(b) Figure 5: Representation of $\mathrm{Sym}(R2.4)$ in the hyperbolic space: (a) without identification and (b) with correct identifications.

Let ${\Delta }_i$ be a triangle of $\mathrm{Tri}(G_{pq})$ with corner vertex $M_i{N}_i{O}_i$ . We denote by $\mathrm{Line}(G_{pq})$ the set of all $N_i{O}_i$ segments of $\mathrm{Tri}(G_{pq})$ which is again a geometrical realization of $\mathrm{Sym}(G_{pq})$ . This group can be viewed as a “double covering” of the medial axis of the associated regular surface. It is represented by red dashed segments and blue segments in Figure 5. In the topological representation, the boundary arrows show where a triangle or a $NO$ segment should be glued. We can use this information to make sure that an element $L\in \mathrm{Line}(G_{pq})$ has the same geometrical position as $L{S}^{-1}T$ . Once all the $L$ and $L{S}^{-1}T$ have the same

Page 5

Regular Surfaces and Regular Maps

geometrical position, we can generate the regular surface by associating to each $NO$ segment a half-tube extending halfway to the middle of one of the tubular edges similar to [6].

4 Boundary Identification

The goal of this Section is to give the elements $L$ and $L{S}^{-1}T\in \mathrm{Line}(G_{pq})$ (red dotted and blue segments on the boundary) the same geometrical position. We do this by using the identifications induced from $\mathrm{Tri}(G_{pq})$ . As stated in the previous section, only the segments of $\mathrm{Line}(G_{pq})$ on the boundary triangle of $\mathrm{Tri}(G_{pq})$ need to be moved. We could also try to do the identification directly on the edges of $\mathrm{Tri}(G_{pq})$ but it is hard if not impossible to resolve the intersecting faces of the triangles after the identification. The identification is combinatorial and to obtain a reasonable 3D initial configuration of the graph, we choose the Jemisphere model of hyperbolic space defined in [13]. The Jemisphere model is a hemisphere like model of the hyperbolic space which is also conformal. Infinity is represented by the equator (Figure 7).

1. identify edge 0

2. head to head at $h_0$

3. tail to tail at $t_0$

4. update and identify side 1

5. head to head at $h_1$

6. tail to tail to $t_1$

7. update and identify side 2

8. head to head at $h_2$

9. tail to tail at $t_2$

10. update and identify side 3

11. head to head at $h_3$

12. connected $\mathrm{Line}(M_T)$ Figure 6: The process of identifying all elements $L\in \mathrm{Line}(M_T)$ to have the same geometrical positions as $L{S}^{-1}T$ and vice versa. On the final shape, each red and blue line in state 1 are pairwise identified.

Suppose, for example, that we want to identify a directed edge $a$ with edge $b$ . Define the tail of $a$ to be $t_a$ and $t_b$ the one of $b$ . Find all segments of $\mathrm{Line}(G_{pq})$ having $t_a$ as endpoint and move these vertices to the

Page 6

Razafindrazaka and Polthier

tail $t_b$ of $b$ . In this process, only the endpoints of $a$ are moved. We do the same for the head $h_a$ of $a$ to the head $h_b$ of $b$ . Once both head and tail are matched, we update the geometrical position of $a$ to be the one of $b$ . We iterate this process until all the boundary $NO$ segments of $\mathrm{Line}(G_{pq})$ are identified. Figure 6 is an illustration of the overall process applied to $\mathrm{Line}(R2.4)$ . It is only a conceptual illustration to show how the identification is done. In state 1, only four elements of $\mathrm{Line}(G_{pq})$ are pairwise at the same geometrical positions (dotted segments are adjacent to continuous segments). The rest need to be moved according to the glueing procedure defined previously. The orange dots represent the edges to be identified. The red dots represent edges to be removed or updated. The algorithm starts by identifying edge 0, first head to head and then tail to tail. Once these are done (state 3), the red dotted line is updated to where it is identified. Then, it continues with edges 1 and 2 with the same strategy. At state 10, there is only one step to be done since the curve 3 is a loop.

Figure 7: R2.4 projected on the Jemisphere model (left) and the resulting identification applied to Line(R2.4) on this model (right).

The input of the algorithm is the set of segments $\mathrm{Line}(G_{pq})$ and the output is again $\mathrm{Line}(G_{pq})$ but the elements $L$ and $L{S}^{-1}T$ have the same geometrical positions.

The identification does not depend on the order of the glueing. The resulting curves and loops are the same. The only problem happens at the end of the identification where the ordering of the segments at the nodes is not well-defined. If we try to derive the regular surface, it might result in a degenerate tubular surface (see Figure 10). We solve this ambiguity in the next section.

5 Construction of the Regular Surface

The regular surface obtained by the tubification of the edge graph of a regular map $G_{pq}$ is also a geometric realization of $\mathrm{Sym}(G_{pq})$ . It is derived by associating to each element $L\in \mathrm{Line}(G_{pq})$ a quarter-tube $Q_L$ . The folding of the quarter tubes depends on the corresponding element in $\mathrm{Sym}(G_{pq})$ . If the element contains $T$ (a continuous segment in $\mathrm{Line}(G_{pq})$ ), then it is folded left. Otherwise, it is folded right. Here, left and right are defined according to the normals from $O$ to $N$ . The geometrical construction of the quarter-tubes is illustrated in Figure 8. The normals along each segment are interpolated from the junctions.

Figure 8: Construction of the quarter tubes.

We call the resulting group $\mathrm{Tub}(G_{pq})$ . For all $Q_L\in \mathrm{Tub}(G_{pq})$ , $Q_L$ and $Q_{L{S}^{-1}T}$ form a half tube. This is possible due to the identification done previously. To have correct tube junctions at the nodes of $\mathrm{Line}(G_{pq})$ ,

Page 7

Regular Surfaces and Regular Maps

it is necessary to have, additionally, each quarter tube $Q_L$ adjacent to $Q_{LT}$ . This is equivalent to having a local ordering of each segment of $\mathrm{Line}(G_{pq})$ at the nodes.

The local ordering at each node is obtained from $\mathrm{Sym}(G_{pq})$ . Suppose that we are at a node $\nu$ which is contained in the segments $L_0,\dots ,L_{2q-1}\in \mathrm{Line}(M_T)$ . The ordering of the segments, as in the hyperbolic space, is reconstructed in a well defined plane at $\nu$ . If $L_0=L$ , then we must find a plane on which $L_1=LT,L_2=LS,\dots ,L_{2q-2}=L{S}^{q-1}$ , and $L_{2q-1}=L{S}^{q-1}T$ . In our implementation, we use this information as a constraint and put $\mathrm{Line}(G_{pq})$ in a spring relaxation procedure. An example of this relaxation procedure is shown in Figure 5 for the case of Line(R2.4). The basic idea is to consider each vertex of the graph as a charge particle attracted by its neighbors and repulsed by the other vertices. This simple physical system gives symmetrical shape but can also get stuck in local minima. For more details on the implementation, we refer to [7, 8]. The resulting tubular surface is illustrated in Figure 10.c.

Figure 9: Spring relaxation of Line(R2.4) with the plane constraint at the junction.

Figure 10.b is an example of such a plane where $q=4$ . Figure 10.a is an example where the spring relaxation is not constrained which induces a degenerate surface. The identification procedure does not guarantee this orientation. Figure 10.c is an example of Line( $G_{pq}$ ) for which $\mathrm{Tub}(G_{pq})$ does not have self-intersections with a well defined tangent plane at the node.

(a) Self intersection

(b) Correct neighbouring at a node

(c) Correct tube junction Figure 10: Wrong ordering at a junction may lead to a degeneracy of the regular surface. The correct ordering is found on a suitable tangent plane.

6 Targetless Visualization of Regular Maps

Unlike regular maps, regular surfaces can always be visualized. One weak point of van Wijk’s approach [6] is that the embedding of a regular surface depends on the embedding of the corresponding regular map. For

Page 8

Razafindrazaka and Polthier

example, the regular surface of the map R2.5{5,10} can be used as a space model of the map R5.8{4,20} but if R2.5 is not embedded, so is R5.8. Our algorithm handles this case and depends only on the regular surface of the target map, not the target map itself. In Figure 11 is our embedding of R5.8 together with its dual.

Figure 11: A realization of the regular map $R5.8\{4,20\}$ (left) and its dual (right).

We find new realizations of regular maps by combining van Wijk’s heuristic [6] with our algorithm. For the purpose of visualization, we show regular maps for which $q$ is not too large and regular surfaces whose number of junctions are not 2 (hosohedral surfaces). We do not show all the regular maps we have found so far (more than 50 new cases), but rather we emphasize on the aesthetic visualization of few realizations in our most symmetric embeddings. These four are our favourite embeddings so far, mapped on the edge graphs of double covered Platonic solids whose branch points are the centers of faces. They are: R9.3’ {6,4} on a 2-Cube, the 6-rings or R13.1’ {12,3} on a 2-Octahedron (this has also a nice relation with the Borromean rings [8]), R21.3’ {6,4} on a 2-Dodecahedron and R37.2’ {15,3} on a 2-Icosahedron, see Figure 12.

R9.3’ on a 2-Cube

R13.1’ on a 2-Octahedron (the 6-rings [8])

R21.3’ on a 2-Dodecahedron

R37.2’ on a 2-Icosahedron Figure 12: High genus regular maps embedded on the regular surfaces of double covered Platonic solids.

Unfortunately, due to the even sided faces of the Cube, we could only achieve one C3 axis and one C2 axis on the double covered geometry. For the other Platonic solids, we only lost the non-oriented symmetry

Page 9

Regular Surfaces and Regular Maps

of the Platonic solids. The double covering of the Tetrahedron gives the Cube, so we do not show any regular maps mapped on its edge graph since the edge graph of the Cube is more symmetric.

R9.6’: 8 val-4 junctions, C2

R9.13’: 1 val-18 junctions, C9

R9.17’: 16 val-3 junctions, C3

R13.1’: 3 val-10 junctions R16.3’: 10 val-5 junctions Figure 13: Some selected high genus regular maps generated by the algorithm. In the first row, junctions are placed manually on a target shape while for the rest, they are automatically generated.

R13.3’: 6 val-5 junctions R17.11’: 8 val-6 junctions junctions

R15.5’: 3 val-9 junctions R25.8’: 12 val-6 junctions

In Figure 13 are more examples of regular maps we succeed in embedding. For the first three surfaces, we succeed in giving a rotational symmetry to the regular maps since the valence of the junctions is not too high except those which have only one junction. As you can see, high valence junctions make the task of getting symmetry hard. Hence, for those classes of regular maps, we only took a minimum of the spring relaxation energy as the final shape.

In Figure 14 are three “really” large genus regular maps generated by our method. For these classes of regular maps, obtaining symmetry is a huge amount of work. Even a non self-intersecting surface is hard to obtain. However, we believe that a careful understanding of the tubes and tiles can improve the symmetry of the shape. R85.8’ is the regular map with the highest genus ever visualized so far (excluding the hosohedral type of surfaces). We asked ourselves how can one find an embedding even with one C2 axis of such a complex topological object?

Page 10

Razafindrazaka and Polthier

R41.3’: 80 val-3 junctions

R61.1’: 120 val-3 junctions

R85.8’: 84 val-4 junctions Figure 14: Some large genus regular maps generated that are intersection free.

The algorithm does not have any limitation as long as the matchings between the regular maps are provided. Van Wijk’s heuristic gives correct matchings of hundreds of regular maps which can all now be visualized using our technique.

In this paper, we showed how to generate an embedding of a regular surface implicitly from a regular map. The regular map itself does not have a priori an embedding. Hence, such maps (for example, R2.5) are not handled by our algorithm. Our algorithm also does not find regular maps for the Hurwitz surfaces. An interesting problem will be to find a similar procedure to realize directly regular maps.

Acknowledgement: We thank Jack van Wijk for his valuable suggestion. We also thank Ulrich Reitebuch for generating the edge graph of the double covered Platonic solids. And finally, we thank the anonymous reviewers for their constructive comments. This research was supported by the DFG-Collaborative Research Center, TRR109, Discretization in Geometry and Dynamics.

References

[1] Beardon A.F., The Geometry of Discrete Groups, Springer Verlag, New York, 1983. [2] Conder M, Regular Maps, August 2012, http://www.math.auckland.ac.nz/~conder/OrientableRegularMaps301.txt. [3] Coxeter H. and Moser W., Generators and Relations for Discrete Groups, Springer Verlag, 1957. [4] Havas G. and Ramsay C., ACE-Advanced Coset Enumerator, 2002, http://www.itee.uq.edu.au/~cram/ce.. [5] Massey W.S, A Basic Course in Algebraic Topology, Graduate Text in Mathematics, Springer-Verlag, 1991. [6] van Wijk J. J., Symmetric Tiling of Closed Surfaces: Visualization of Regular Maps. Proc. SIGGRAPH 2009, 49:1-12, 2009. [7] Razafindrazaka F., Visualization of High Genus Regular Maps, master’s thesis, Freie Universität Berlin, 2012, http://page.mi.fu-berlin.de/faniry/files/faniry/masterThesis_2012.pdf. [8] Razafindrazaka F. and Polthier K., The 6-ring, In Proc. BRIDGES 2013 Conference, Entschede, Netherlands, 279-286. [9] Reid M. and Szendro B, Geometry and Topology, Cambridge University Press, 2005. [10] Séquin C. H., Patterns on the Genus-3 Klein quartic, In Proc. BRIDGES 2006 Conference, London, 245-254. [11] Séquin C. H., Symmetric Embedding of Locally Regular Hyperbolic Tilings, In Proc. BRIDGES 2007 Conference, San Sebastian, 379-388. [12] Séquin C. H., My Search for Symmetrical Embeddings of Regular Maps, In Proc. BRIDGES 2010 Conference, Hungary, 85-94. [13] Cannon J. W., Floyd W. J. and Kenyon R., Hyperbolic geometry, Flavors of Geometry, MSRI Publications, Volume 31, 1997.