Jérémie Bettinelli

École polytechnique
Laboratoire d'informatique (LIX)
91128 Palaiseau Cedex
E-mail: firstname « . » lastname « at » normalesup « . » org
Office: 2023
Phone: (+33) (0)1 77 57 80 61
Désolé, pas de version française

Computer simulations of random maps


Sketchfab pagePicture page

This page is dedicated to computer simulations of random maps. You may visit my Sketchfab page for more similar simulations. You may also visit my picture page to see all the pictures at a glance. All the maps are embedded using a spring electrical embedding. It means that the computer tries to minimize an energy given by an electrical type of repulsion between vertices and a spring force between vertices that are linked through an edge. The advantage of such an embedding is that it reflects as best as possible the intrinsic metric of the map. Sometimes, some extra constraints are imposed, as for example in the case of cactus embeddings. See the second to last section for a more detailed explanation of what is shown on the pictures.

Click on any 3D simulation in order to rotate the picture (left click), zoom in and out (wheel), pan (right click on SHIFT + left click) or wander wherever you want.

Simulation pages

How can I use these models/pictures?

There are several ways to proceed, depending on what you want to do. You may simply download the 3D pdf, jpg, gif or pdf files. Note that the pdf files are very large and the jpg/gif files are provided in a reasonable aspect/size ratio. If, however, you want better quality images, just contact me and I will provide them. You may also do the following:

What do we see exactly on these pictures?

Except for the cactus embeddings, all the quadrangular faces are split into 4 subtriangles (by adding one vertex at the center) that are then drawn in 3D. (This explains why sketchfab always counts 4 times the number of faces I announce.) On some pictures, one can actually see that the edges of the map do not have the same color as the extra 4 edges linking the vertices to the center of the face. For example, the following figure depicts a plane quadrangulation with 10 faces. The thick purple edges are the edges of the quadrangulation and the thin ones are the extra ones.

Brownian map
Plane quadrangulation with 10 faces

Moreover, a quadrangulation is very likely to contain multiple edges. These edges are all drawn, but unfortunately at the exact same location, so that the surface we see is not exactly the one we want. A multiple edge will "squeeze" the surface and we still need some imagination to "open up" these multiple edges, as if it were an old purse. In other words, if we were to travel inside the surface, we should be able to pass through these multiple edges. On the previous picture, there are 3 double edges. One clearly sees two "bubbles" consisting in 4 faces, linked by a double edge. On every bubble is grafted one "flat" face by a double edge.

In the case of the cactus embeddings, the faces are split into 2 subtriangles by adding one of the two diagonals.

Finally, beware that you see an embedding of the underlying graph with faces added a posteriori. In particular, it is possible (though unlikely) for the faces to cross themselves. Another downside that you may observe on some pictures is that the boundary components might be intertwined.


You may also visit the following pages for related computer simulations:

Valid XHTML 1.0 Strict