Wednesday, July 31, 2013

Generating completely foldable triangulations

Tripartite subdivision of an icosahedron.

When the triangles of the above mesh are made equilateral, the resulting polyhedron (a stellation of the rhombic triacontahedron) is completely foldable. The paper model itself is rigid, but the surface has an alternate conformation as a stack of triangles.

As shown by Di Francesco and Guitter, the necessary and sufficient condition for a closed surface composed of equilateral triangles to be completely foldable is that its graph is tripartite. Given a surface mesh (or, topologically speaking, a map,) they teach a simple way to generate a tripartite triangulation (triangle-faced map) of the same surface.

Construction: Given a map with black vertices, bisect every edge with a white vertex; place a pink vertex in the center of each face and connect it to the white and black vertices incident to that face.

The construction is equivalent to the map operation Meta (a.k.a. barycentric subdivision, full bisection, 2-D subdivision, dual triangle quadrisection,) and as well the construction that locates the preimages of 0, 1, and ∞ in a dessin d'enfants.

Completely foldable surfaces

What kinds of closed, triangulated surfaces can be completely folded up into a single triangle?

The classic interest of origami is folding up a portion of the plane (usually a square sheet of paper) into a more appealing or useful shape, but physicists interested in 2-D quantum gravity have been looking at folding from a different direction: what kinds of closed, triangulated surfaces can be folded up into a small triangular portion of the plane?

Di Francesco and Guitter have shown that any vertex-tricolorable mesh of equilateral triangles can be phantom-folded to a single triangle. By phantom-folding we mean that the surface is allowed to pass through and coincide with itself in its folded state; by vertex-tricolorable (a.k.a., properly 3-colorable, or tripartite) we mean that we can assign one of three colors to each vertex of the mesh such that no two adjacent vertices receive the same color. When completely folded into a single triangle—or even just partially folded onto the plane—we find that the coincident vertices share the same color. Di Francesco and Guitter's result holds for any genus of surface, orientable or not.

Vertex-tricoloring a triangulation is rigid: coloring the three vertices of a single triangle forces all the rest. The coloring goes easily or not at all. The underlying graph must be tripartite for the coloring to succeed. Whenever an equilateral triangulation folds onto a portion of the plane, it has three vertex classes, and their spatial arrangement will conform exactly to a vertex tricoloring of the plane equivalent to this one. A subsidiary tricoloring of edges (not a proper edge coloring) results by simply mixing the vertex colors of each edge's endpoints. This edge coloring does direct a proper edge coloring of the dual, trivalent graph that describes the triangles' connectivity.

A surface mesh composed of equilateral triangles necessarily gives a rather crinkled approximation to a smooth surface (see image below.) Adding a requirement of vertex-tricolorability exacerbates this. A necessary (but not sufficient) condition for vertex-tricolorability is that there be an even number of triangles around each vertex. (Place three—or any odd number—of equilateral triangles around a vertex and try folding the ensemble flat!) That means surface curvature can only be coded by clusters of 6, 4, 8, etc., equilateral triangles around a vertex—we forfeit the option to approximate surface curvature with clusters of 3, 5, 7, etc., triangles. Completely foldable surfaces will in general look quite crumpled even in their fully extended state. C'est la vie.


A surface composed of equilateral triangles is crinkly-looking even before we require the triangulation to be Eulerian (i.e., to have an even number of triangles around each vertex, such a triangulation is locally tripartite.) Image quoted from Isenburg, Gumhold and Gotsman, "Connectivity Shapes."

By the way, to physicists, the curvature we are talking about is the quantized gravitational curvature of a 2-D spacetime, a curvature induced by the presence of matter. Constraints that we may find vitally useful (i.e., foldability) sometimes just make for more interesting behavior in their models.