Flattening a 4-D Cube onto Your Desk with Graph Theory | by Rohit Pandey | Sep, 2022
Exploring higher dimensional objects with computer science algorithms
The applicability of graph theory in the context of web2.0 is obvious, with websites like Facebook (undirected graph of friendships) and Twitter (directed graph of followings) built around them. Another obvious application is in computer networks. The field of operations research, which started with applying math to the field of battlefield logistics is chock full of graph theory problems as well. For instance, see here.
But graph theory is so versatile, it finds applications in data science as well. Apart from the fact that neural networks are special kinds of graphs, it is front and center in the field of combinatorial testing, where we design experiments in a way that important properties or combinations of properties are covered. For instance, see here. This is the context in which I first started learning about it.
In this article, we’ll be covering a different application however. Since I was a child, I was fascinated with the four dimensional cube. I wanted to hold it in my hand and manipulate it like I can with a 3-d cube. Little did I know that the missing piece was graph theory (a tool I added to my arsenal only recently as a result of its applications in data science), as we will see.
I-A) Flattening a cube
A cube is an object that lives in 3-dimensional space and is familiar to most (think boxes). It has six identical square faces and 12 edges between some of those faces. What do you do with cubical boxes? You cut them open (to see what’s inside). This is often done by cutting along the edges. There are ways to do this such that the six faces still stay connected to the main body and lie flat on the floor. It turns out there are 11 topologically distinct (meaning you can’t translate and rotate one and make it perfectly overlap with any other) meshes that emerge when we make the cuts in different ways. These are shown below.
Notice that in each of the meshes, there are exactly five surviving edges. This isn’t a coincidence. If we think of the faces of the cube as the vertices of a graph and the surviving edges as the edges of that graph, then each of the meshes in the figure above is a spanning tree. Which means that there is exactly one path that connects any two vertices. Since there were twelve edges in the original cube, we cut exactly seven of them to get any of the eleven meshes. The total number of ways of selecting the seven edges to cut is {12 \choose 7} = 792. But a lot of those don’t lead to spanning trees since one or two of the faces are completely isolated from the rest of the body. It turns out that slightly less than half of those cuts lead to spanning trees, 384. And every spanning tree leads to a valid mesh. Among those 384 meshes, most are repetitions of previously seen ones if we rotate and translate them (meaning they are topologically equivalent). In other words, if we can place one mesh on another in any way such that the latter completely covers the former, those two are considered the same mesh. So only 11 topologically distinct ones pictured above emerge.
It is unclear when some human first counted out these 11 meshes. It is a problem that can be solved in a reasonable amount of time without a computer. So whether or not it was considered and solved before the advent of computers is an interesting question. Most authors today reference [1] from 1984. In [2], Gardner poses the question on how many meshes exist and it appears he knew the answer (in 1966), though he doesn’t state it explicitly.
If you’re wondering about applications of this kind of thing, BTW, one example is solar sails which must be compact while launching and unfold into something with a large surface area.
I-B) Flattening a Tesseract
The concept of a cube exists can be extended to space of any dimensionality. In two dimensions, we have the square. And in four dimensions, we get a Tesseract, a four dimensional object composed of three dimensional cubes. Just like a 3-d cube can be flattened into 2-d space to form a mesh of squares, so can a Tesseract be flattened into 3-d space to form a mesh of 3-d cubes.
The question on how many such meshes exist was posed in 1966 by Gardner (see page x of [2]). Answered in 1985 (261 meshes) in [1] through a new concept called “paired trees”. The meshes were finally visualized in 2015 in the MathOverflow post, [3].
What no one seems to have considered so far is flattening a 4-d cube all the way to 2-d space into a mesh of squares. This is what we’ll explore in section III. But first, let’s describe some notation.
In this section, we establish some notation for identifying the various elements of an n-dimensional cube. Let’s start with a 2-d cube or a square. We place it in a way that the center of the square is at the origin, (0,0) as shown in figure 2 below.
For brevity, we call the entire square “00” because its center of mass happens to lie at (0,0). The center of the top edge of the square is (0,+1). Again, for the sake of brevity, we name it just “0+”. Similarly, the bottom edge is named 0-. The left edge is “-0” and the right one is “+0”. The top left vertex is (-1,+1) and so we call it “-+” and so on.
For any given entity of the cube in d-dimensional space, its name is represented by d characters, each of which can be one of -, 0 or +. A string of all zeros is the center of the cube (and there is only one). One of the zeros replaced by either a + or a — becomes a set of (d-1) dimensional cubes. There are 2*d such cubes (d ways of choosing where the non-zero character will lie and then assigning it either a + or a -). Similarly, there are d*(d-1)/2*4 = 2*d*(d-1) cubes of dimension (d-2) (choose two locations that for the non-zero characters and then fill then both with “+” or “-” in 4 ways) and so on.
We saw in section (I) how it was possible to flatten a 3-d cube to a 2-d table such that all the faces stayed connected and none of them overlapped. Is it possible to do the same thing with a 4-d cube or Tesseract? Somewhat surprisingly, the answer is yes. Shown below is one such mesh. I obtained it by carefully flattening out just the “top” 3-d cube to a table with some of the faces still attached, and then trying to flatten the remaining faces by hit and trial in a way that they wouldn’t overlap.
The obvious question is, how many such meshes exist?
III-A) Properties of valid meshes
For the valid meshes of a cube from figure-1, we note two key properties that also hold for the mesh of a Tesseract in figure-2:
- It’s clear that all the faces are still connected to each other (by definition). So, it is possible to start at any of the faces in the mesh and reach any other.
- Also note that between any two faces, there is at most one edge. This was true of the original Cube or Tesseract, so it must be true of the mesh as well.
Combining the above two facts and thinking of the faces of the solid as vertices of a graph, it is clear that the mesh forms a spanning tree (a graph with all vertices reachable from any vertex and at most one edge between any two vertices). This insight was probably the first step used by Turney in [1] to count the 3-d meshes of a Tesseract. So, every valid 2-d mesh of a cube or Tesseract (or for that matter, any (d<n) dimensional mesh of an n-dimensional cube) is a valid spanning tree if the faces are considered vertices of a graph. One property of a spanning tree with n vertices is that it has exactly n-1 edges. Let’s visualize this graph of the faces of the Tesseract from which the spanning trees that then become the meshes are constructed.
For the case of the cube, each physical edge maps 1:1 with a graph edge (this might seem obvious, but you’ll see later why I called it out). So, we start with 12 edges and have to cut exactly 7 edges (so 6–1=5 remain) before “opening it up” into a mesh (which is why all the meshes in figure 1 had 5 edges connected). Once we make the 7 cuts (in a way that all the vertices remain reachable from each other), there is only one way to flatten to a mesh.
For a Tesseract, each physical edge actually corresponds to three edges of the graph. This is because three faces meet at every physical edge (as opposed to 2 for a cube). So while the number of physical edges is just 32, the number of graph edges (in the graph where each face is a vertex) is actually 32*3 = 96 (3 ways to choose 2 of the faces meeting at each physical edge). Of these 96 graph edges, only 23 can remain in the flattened mesh. For a given physical edge, if all three graph edges are intact, it will be impossible to flatten the Tesseract to a table without overlap.
IV-A) The basic operation
Let’s say we have a spanning tree of the Tesseract face graph that can be flattened into a mesh, expressed as an adjacency list. How do we go from this graph to the actual flattened Tesseract mesh (like figure-2)? We can imagine doing this by rotating the faces as we would in the physical world. Any two connected faces of the d-dimensional cube are perpendicular. For example, two faces (per nomenclature in section II) 00- and -00 of the 3-d cube. Note that in the figures of this section, I’ve shifted the origin from the center of the cube to one of the vertices to make the flattening process clearer.
We can always fix one of the faces and rotate the other one to its plane along the edge connecting them as shown in the figure above. This is the basic operation we’ll build on top of. Note that no matter how large the dimensionality of the space this unfolding happens in, the initial and final configurations are unique. There is always a simple rotation about the common edge joining the two faces (here, the y-axis) which can be expressed in matrix form. In the example above, this rotation matrix (rotation in the x-z plane) is:
One subtlety when performing this on a computer is that the rotation (depending on weather the angle is positive or negative) could bring the -00 face on top of or adjacent to the 00- face. We want to avoid the rotation that makes the faces overlap. If plugging in \pi/2 into the rotation matrix causes the faces to overlap, we simply plug in -\pi/2.
IV-B) Two simple meshes
Now, let’s take just three faces of a 3-d cube. Say 00-, 0–0 and -00. These three faces are shown in the figure below.
In the original cube, they are all connected to each other. The face graph of these three faces would look like the figure 7-a.
But this isn’t a tree. In a tree, there is only one path between any two vertices. In the graph above, there are two paths between -00 and 0–0 (direct and via the third vertex, 00-). To make it a tree, we have to cut off one of the edges. In figure 3-b we choose to cut the top edge between -00 and 0–0. Now that we have a tree, we need to get the corresponding mesh.
First, we select the face whose plane all other faces are going to rotate into in the flattened mesh. If we were opening up a cubical box, this would be the face that rests on the floor. This one is the “base face” and the choice is arbitrary. In the example above, we choose 00- (the bottom face in the figure) as the base face.
Here, the remaining two faces are connected directly to the base face. We can simply rotate both of them down to the plane of the base face independently, as in the “basic operation” described earlier, obtaining the mesh below.
This was an easy example, with both faces we had to rotate directly connected to the base face. Let’s go back to figure 7-a and this time cut the edge between 0–0 and 00-. We get another valid spanning tree. And let’s keep the base face the same, 00-.
Now, we have to do the rotations in two steps. The 0–0 face is connected to the -00 face. If we rotate the -00 face first, the rotation required to bring the 0–0 face to its plane (the rotation matrix as well as axis about which to rotate) will change (since everything would have rotated now). To avoid this, we rotate the 0–0 face and bring it into the plane of -00 first. Only then do we bring both those faces to the x-y plane where the 00- face lies. This sequence of operations is demonstrated below.
Note that here, the 0–0 face needed two rotations since it was two hops from the base face (00-) in the tree while the -00 face needed one rotation since it was one hop from the base face. Armed with the intuition from these two cases, we can develop a general algorithm for flattening a cube into a 2-d mesh, given the spanning tree of the edges we choose to preserve.
IV-C) Algorithm for performing the rotations
An algorithm can be devised that applies the rotations to all the faces in the right order, given the spanning tree to go from the d-dimensional cube to the mesh. First, we know that all faces of the cube need to be visited (and certain operations must be performed to the faces in those visits). Since the faces are expressed as a graph, a graph exploration algorithm is the first thing that comes to mind (algorithms that explore all the vertices of a graph).
The simplest and most well known graph exploration algorithm is called depth first search (DFS; see section 22.3 of Introduction to Algorithms by Cormen et.al., [4]). We apply it not on the original graph of the Tesseract, but on the spanning tree (which is also a graph, just with a much smaller number of edges), starting at the base face. This is because it is the spanning tree that maps to the mesh we’re after.
The basic operation(s) we need to perform on all faces are rotations to bring them to the same plane as the base face. As we go from one face to the next (performing DFS), we know the rotation required to bring the latter to the same plane as the former per section IV-A. Since we start at the base face (b), that is the only face that doesn’t get any rotation. The faces directly connected to the base face (let’s call them the “first layer of faces”) in the spanning tree get one rotation. Those connected to this first layer of faces (the “second layer”) get two rotations (first to bring them to the same plane as the respective first layer faces and then to that of the base face).
For any given face (say f), there is a path from the base face (b) to it in the tree. Starting at the base face, b, each new face encountered along this path has a corresponding rotation that can be applied to it to bring it to the same plane as the previous face in the path. Each of these rotations accumulated along the path must be applied to the given face, f. We can keep a record of all these rotations via the depth first search on the tree. There is a concept of vertex colors in DFS (again, refer to section 22.3 of Cormen et.al, [4]) that can be white, grey or black. White means the vertex of the graph (or tree) hasn’t even been encountered yet (all vertices are white at the start of the algorithm). Grey means it’s been visited but all the vertices downstream from it in the exploration haven’t been processed and black means the algorithm is done processing the vertex and all its downstream vertices as well (once the algorithm completes, all vertices are black). As long as we’re still traversing a path (haven’t completed it), all vertices encountered along that path will be marked grey. And so, we can maintain a list of rotations to be performed corresponding to each grey vertex (or face). When a vertex is marked black, we simply remove the corresponding rotation from the list.
However, the order in which these rotations are applied to a given face (f) is also important as we saw in the second example of the mesh with three faces from section IV-B. The given face should first be rotated to the plane of the face it is directly connected to, then to the one before it in the path and so on, reverse order until it is finally in the same plane as the base face. This ensures that we don’t have to update the rotations as other rotations happen. The “stack” data structure is perfect for this since it has a “last in first out” property (think of a stack of dirty dishes).
So instead of applying all the rotations corresponding to the grey vertices as we encounter the faces, we store the rotation and the face it is to be applied to in a stack. Once the depth first search has completed exploring all vertices, we actually apply the rotations by popping one at a time from the stack the faces and corresponding rotations to be applied. Below is a visual demonstration of this algorithm going from the Tesseract to the mesh by performing the required sequence of rotations.
And here is a Python implementation of the above algorithm.
Here is a video where this algorithm is applied to the familiar 3-d cube:
When we saw our first 2-d mesh in section III (figure 3), we asked how many there are. And in the absence of an exact answer, we’d like upper and lower bounds that are as tight as possible.
We’ll describe in section VI, a way to generate random meshes starting with one of them. If we then keep only the topologically distinct meshes, we’ll build not only a library of meshes, but also a computational lower bound, which is the distinct number we’ve managed to collect. Any theoretical lower bound will ultimately be superseded by the computational one. So far, the algorithm (I run it once in a while for 10 minutes and add to the mesh collection) has managed to collect about 600 distinct meshes (and this count is always increasing). The current computational lower bound on the number of 2-d meshes of a Tesseract is therefore 600.
For the upper bound, recall the algorithm in section IV-C which generates a valid mesh from a spanning tree of the face graph whenever this is possible (which very often isn’t). And even among the meshes we get this way, there will be versions that are topologically similar to other meshes seen previously. So, the number of spanning trees should be a comfortable upper bound on the number of distinct meshes.
Moreover, since every mesh corresponds to a unique spanning tree (but a spanning tree might not yield a mesh), one way to count the number of meshes (while building a library of them as well) is to loop through all possible spanning trees. For each one, we check if a mesh is possible and if it also happens to be a “topologically novel” one (meaning we haven’t seen any before that its topologically similar to), we save it somewhere.
The problem is that the number of spanning trees turns out to be 10²⁰ (can be obtained by applying Kirchhoff’s matrix tree theorem to the graph in figure-4). So, even if we take a milli second to process a single spanning tree, it’ll take more than the current age of the universe so far to exhaust all of them. The only thing we get from this line of attack is thus a very generous upper bound on the number of meshes. There are ways to improve on this, but we won’t get into them for now, since they still keep the upper bound at astronomically high numbers.
The algorithm in section IV-C will always give us a mesh corresponding to a spanning tree if such a mesh is possible (which often isn’t the case). If we have a way to iterate over spanning trees, we can generate a mesh where possible
As mentioned in the previous section, one way to get a lower bound on the number of distinct meshes is to simply start generating them and eliminating the ones that are topologically the same as a mesh seen before. Such an algorithm will keep “collecting” meshes, a bit like the coupon collectors problem and maintaining a “library” of distinct meshes seen so far. A problem with this approach is that we’ll never know for sure if and when we’ve seen all meshes. When we’re very close to generating all meshes, it’ll become harder and harder to “collect” any more. Towards the end, almost every mesh we randomly draw will have been seen before. And so, if we’ve generated a lot of meshes without running across a new one, it could be because we’ve simply completed our collection or that a few are left and it has just become really hard to see a new one when drawing randomly.
For now, we choose to live with this drawback and simply collect as many meshes as we can. Our algorithm has two parts.
The first starts with a given mesh and generates another valid random mesh from it, that is guaranteed to be different from the previous one. This is done by cutting the edge between two connected faces of the first mesh. This creates two sub-meshes and also two sub-trees (the original spanning tree has been cut in two). Then, we find another two faces (one from the first sub-mesh, one from the second) to “paste” the two sub-trees together and create a new spanning tree. Since the two “sub-trees” are connected again, the property of being able to go from any face to any other face is re-instated. And then, we can use the algorithm in section IV-C to see if this new tree generates a valid mesh. If it doesn’t, we simply generate a new tree and keep going until we find another valid mesh. The mesh is saved to disk as a text file, which is the adjacency list of the corresponding spanning tree.
The second part compares the new mesh with all existing meshes and removes the ones that have been seen before.
These ideas are implemented in the following Python code: https://github.com/ryu577/pyray/blob/master/pyray/shapes/twod/tst_sq_mesh.py. The second part is really the computational bottle neck. The more meshes we collect, the more expensive it becomes to compare a new mesh to all the previous ones. As mentioned, this two-part algorithm can be run in a loop forever until it becomes extremely, extremely hard to find new meshes.
The problem of enumerating the 2-d meshes of a 4-d cube has two hallmarks of the most popular Math problems. It’s easy to explain and frame in a way that almost anyone can understand it. At the same time, it seems that even our most sophisticated tools are falling short of solving it. At a minimum, we can unleash our computing power on this problem and discover close to all the meshes.
_______________________________________________________
If you liked the story, become a referred member 🙂
https://medium.com/@rohitpandey576/membership
[1] Paper 1984 where 3-d meshes are mapped to paired trees (https://unfolding.apperceptual.com).
[2] Martin Gardner’s book from 1966 (“The colossal book of mathematics”: https://www.logic-books.info/sites/default/files/the_colossal_book_of_mathematics.pdf)
[3] MathOverflow post where all distinct 3-d meshes are plotted (https://mathoverflow.net/questions/198722/3d-models-of-the-unfoldings-of-the-hypercube/)
[4] Introduction to algorithms by Cormen et.al.
Exploring higher dimensional objects with computer science algorithms
The applicability of graph theory in the context of web2.0 is obvious, with websites like Facebook (undirected graph of friendships) and Twitter (directed graph of followings) built around them. Another obvious application is in computer networks. The field of operations research, which started with applying math to the field of battlefield logistics is chock full of graph theory problems as well. For instance, see here.
But graph theory is so versatile, it finds applications in data science as well. Apart from the fact that neural networks are special kinds of graphs, it is front and center in the field of combinatorial testing, where we design experiments in a way that important properties or combinations of properties are covered. For instance, see here. This is the context in which I first started learning about it.
In this article, we’ll be covering a different application however. Since I was a child, I was fascinated with the four dimensional cube. I wanted to hold it in my hand and manipulate it like I can with a 3-d cube. Little did I know that the missing piece was graph theory (a tool I added to my arsenal only recently as a result of its applications in data science), as we will see.
I-A) Flattening a cube
A cube is an object that lives in 3-dimensional space and is familiar to most (think boxes). It has six identical square faces and 12 edges between some of those faces. What do you do with cubical boxes? You cut them open (to see what’s inside). This is often done by cutting along the edges. There are ways to do this such that the six faces still stay connected to the main body and lie flat on the floor. It turns out there are 11 topologically distinct (meaning you can’t translate and rotate one and make it perfectly overlap with any other) meshes that emerge when we make the cuts in different ways. These are shown below.
Notice that in each of the meshes, there are exactly five surviving edges. This isn’t a coincidence. If we think of the faces of the cube as the vertices of a graph and the surviving edges as the edges of that graph, then each of the meshes in the figure above is a spanning tree. Which means that there is exactly one path that connects any two vertices. Since there were twelve edges in the original cube, we cut exactly seven of them to get any of the eleven meshes. The total number of ways of selecting the seven edges to cut is {12 \choose 7} = 792. But a lot of those don’t lead to spanning trees since one or two of the faces are completely isolated from the rest of the body. It turns out that slightly less than half of those cuts lead to spanning trees, 384. And every spanning tree leads to a valid mesh. Among those 384 meshes, most are repetitions of previously seen ones if we rotate and translate them (meaning they are topologically equivalent). In other words, if we can place one mesh on another in any way such that the latter completely covers the former, those two are considered the same mesh. So only 11 topologically distinct ones pictured above emerge.
It is unclear when some human first counted out these 11 meshes. It is a problem that can be solved in a reasonable amount of time without a computer. So whether or not it was considered and solved before the advent of computers is an interesting question. Most authors today reference [1] from 1984. In [2], Gardner poses the question on how many meshes exist and it appears he knew the answer (in 1966), though he doesn’t state it explicitly.
If you’re wondering about applications of this kind of thing, BTW, one example is solar sails which must be compact while launching and unfold into something with a large surface area.
I-B) Flattening a Tesseract
The concept of a cube exists can be extended to space of any dimensionality. In two dimensions, we have the square. And in four dimensions, we get a Tesseract, a four dimensional object composed of three dimensional cubes. Just like a 3-d cube can be flattened into 2-d space to form a mesh of squares, so can a Tesseract be flattened into 3-d space to form a mesh of 3-d cubes.
The question on how many such meshes exist was posed in 1966 by Gardner (see page x of [2]). Answered in 1985 (261 meshes) in [1] through a new concept called “paired trees”. The meshes were finally visualized in 2015 in the MathOverflow post, [3].
What no one seems to have considered so far is flattening a 4-d cube all the way to 2-d space into a mesh of squares. This is what we’ll explore in section III. But first, let’s describe some notation.
In this section, we establish some notation for identifying the various elements of an n-dimensional cube. Let’s start with a 2-d cube or a square. We place it in a way that the center of the square is at the origin, (0,0) as shown in figure 2 below.
For brevity, we call the entire square “00” because its center of mass happens to lie at (0,0). The center of the top edge of the square is (0,+1). Again, for the sake of brevity, we name it just “0+”. Similarly, the bottom edge is named 0-. The left edge is “-0” and the right one is “+0”. The top left vertex is (-1,+1) and so we call it “-+” and so on.
For any given entity of the cube in d-dimensional space, its name is represented by d characters, each of which can be one of -, 0 or +. A string of all zeros is the center of the cube (and there is only one). One of the zeros replaced by either a + or a — becomes a set of (d-1) dimensional cubes. There are 2*d such cubes (d ways of choosing where the non-zero character will lie and then assigning it either a + or a -). Similarly, there are d*(d-1)/2*4 = 2*d*(d-1) cubes of dimension (d-2) (choose two locations that for the non-zero characters and then fill then both with “+” or “-” in 4 ways) and so on.
We saw in section (I) how it was possible to flatten a 3-d cube to a 2-d table such that all the faces stayed connected and none of them overlapped. Is it possible to do the same thing with a 4-d cube or Tesseract? Somewhat surprisingly, the answer is yes. Shown below is one such mesh. I obtained it by carefully flattening out just the “top” 3-d cube to a table with some of the faces still attached, and then trying to flatten the remaining faces by hit and trial in a way that they wouldn’t overlap.
The obvious question is, how many such meshes exist?
III-A) Properties of valid meshes
For the valid meshes of a cube from figure-1, we note two key properties that also hold for the mesh of a Tesseract in figure-2:
- It’s clear that all the faces are still connected to each other (by definition). So, it is possible to start at any of the faces in the mesh and reach any other.
- Also note that between any two faces, there is at most one edge. This was true of the original Cube or Tesseract, so it must be true of the mesh as well.
Combining the above two facts and thinking of the faces of the solid as vertices of a graph, it is clear that the mesh forms a spanning tree (a graph with all vertices reachable from any vertex and at most one edge between any two vertices). This insight was probably the first step used by Turney in [1] to count the 3-d meshes of a Tesseract. So, every valid 2-d mesh of a cube or Tesseract (or for that matter, any (d<n) dimensional mesh of an n-dimensional cube) is a valid spanning tree if the faces are considered vertices of a graph. One property of a spanning tree with n vertices is that it has exactly n-1 edges. Let’s visualize this graph of the faces of the Tesseract from which the spanning trees that then become the meshes are constructed.
For the case of the cube, each physical edge maps 1:1 with a graph edge (this might seem obvious, but you’ll see later why I called it out). So, we start with 12 edges and have to cut exactly 7 edges (so 6–1=5 remain) before “opening it up” into a mesh (which is why all the meshes in figure 1 had 5 edges connected). Once we make the 7 cuts (in a way that all the vertices remain reachable from each other), there is only one way to flatten to a mesh.
For a Tesseract, each physical edge actually corresponds to three edges of the graph. This is because three faces meet at every physical edge (as opposed to 2 for a cube). So while the number of physical edges is just 32, the number of graph edges (in the graph where each face is a vertex) is actually 32*3 = 96 (3 ways to choose 2 of the faces meeting at each physical edge). Of these 96 graph edges, only 23 can remain in the flattened mesh. For a given physical edge, if all three graph edges are intact, it will be impossible to flatten the Tesseract to a table without overlap.
IV-A) The basic operation
Let’s say we have a spanning tree of the Tesseract face graph that can be flattened into a mesh, expressed as an adjacency list. How do we go from this graph to the actual flattened Tesseract mesh (like figure-2)? We can imagine doing this by rotating the faces as we would in the physical world. Any two connected faces of the d-dimensional cube are perpendicular. For example, two faces (per nomenclature in section II) 00- and -00 of the 3-d cube. Note that in the figures of this section, I’ve shifted the origin from the center of the cube to one of the vertices to make the flattening process clearer.
We can always fix one of the faces and rotate the other one to its plane along the edge connecting them as shown in the figure above. This is the basic operation we’ll build on top of. Note that no matter how large the dimensionality of the space this unfolding happens in, the initial and final configurations are unique. There is always a simple rotation about the common edge joining the two faces (here, the y-axis) which can be expressed in matrix form. In the example above, this rotation matrix (rotation in the x-z plane) is:
One subtlety when performing this on a computer is that the rotation (depending on weather the angle is positive or negative) could bring the -00 face on top of or adjacent to the 00- face. We want to avoid the rotation that makes the faces overlap. If plugging in \pi/2 into the rotation matrix causes the faces to overlap, we simply plug in -\pi/2.
IV-B) Two simple meshes
Now, let’s take just three faces of a 3-d cube. Say 00-, 0–0 and -00. These three faces are shown in the figure below.
In the original cube, they are all connected to each other. The face graph of these three faces would look like the figure 7-a.
But this isn’t a tree. In a tree, there is only one path between any two vertices. In the graph above, there are two paths between -00 and 0–0 (direct and via the third vertex, 00-). To make it a tree, we have to cut off one of the edges. In figure 3-b we choose to cut the top edge between -00 and 0–0. Now that we have a tree, we need to get the corresponding mesh.
First, we select the face whose plane all other faces are going to rotate into in the flattened mesh. If we were opening up a cubical box, this would be the face that rests on the floor. This one is the “base face” and the choice is arbitrary. In the example above, we choose 00- (the bottom face in the figure) as the base face.
Here, the remaining two faces are connected directly to the base face. We can simply rotate both of them down to the plane of the base face independently, as in the “basic operation” described earlier, obtaining the mesh below.
This was an easy example, with both faces we had to rotate directly connected to the base face. Let’s go back to figure 7-a and this time cut the edge between 0–0 and 00-. We get another valid spanning tree. And let’s keep the base face the same, 00-.
Now, we have to do the rotations in two steps. The 0–0 face is connected to the -00 face. If we rotate the -00 face first, the rotation required to bring the 0–0 face to its plane (the rotation matrix as well as axis about which to rotate) will change (since everything would have rotated now). To avoid this, we rotate the 0–0 face and bring it into the plane of -00 first. Only then do we bring both those faces to the x-y plane where the 00- face lies. This sequence of operations is demonstrated below.
Note that here, the 0–0 face needed two rotations since it was two hops from the base face (00-) in the tree while the -00 face needed one rotation since it was one hop from the base face. Armed with the intuition from these two cases, we can develop a general algorithm for flattening a cube into a 2-d mesh, given the spanning tree of the edges we choose to preserve.
IV-C) Algorithm for performing the rotations
An algorithm can be devised that applies the rotations to all the faces in the right order, given the spanning tree to go from the d-dimensional cube to the mesh. First, we know that all faces of the cube need to be visited (and certain operations must be performed to the faces in those visits). Since the faces are expressed as a graph, a graph exploration algorithm is the first thing that comes to mind (algorithms that explore all the vertices of a graph).
The simplest and most well known graph exploration algorithm is called depth first search (DFS; see section 22.3 of Introduction to Algorithms by Cormen et.al., [4]). We apply it not on the original graph of the Tesseract, but on the spanning tree (which is also a graph, just with a much smaller number of edges), starting at the base face. This is because it is the spanning tree that maps to the mesh we’re after.
The basic operation(s) we need to perform on all faces are rotations to bring them to the same plane as the base face. As we go from one face to the next (performing DFS), we know the rotation required to bring the latter to the same plane as the former per section IV-A. Since we start at the base face (b), that is the only face that doesn’t get any rotation. The faces directly connected to the base face (let’s call them the “first layer of faces”) in the spanning tree get one rotation. Those connected to this first layer of faces (the “second layer”) get two rotations (first to bring them to the same plane as the respective first layer faces and then to that of the base face).
For any given face (say f), there is a path from the base face (b) to it in the tree. Starting at the base face, b, each new face encountered along this path has a corresponding rotation that can be applied to it to bring it to the same plane as the previous face in the path. Each of these rotations accumulated along the path must be applied to the given face, f. We can keep a record of all these rotations via the depth first search on the tree. There is a concept of vertex colors in DFS (again, refer to section 22.3 of Cormen et.al, [4]) that can be white, grey or black. White means the vertex of the graph (or tree) hasn’t even been encountered yet (all vertices are white at the start of the algorithm). Grey means it’s been visited but all the vertices downstream from it in the exploration haven’t been processed and black means the algorithm is done processing the vertex and all its downstream vertices as well (once the algorithm completes, all vertices are black). As long as we’re still traversing a path (haven’t completed it), all vertices encountered along that path will be marked grey. And so, we can maintain a list of rotations to be performed corresponding to each grey vertex (or face). When a vertex is marked black, we simply remove the corresponding rotation from the list.
However, the order in which these rotations are applied to a given face (f) is also important as we saw in the second example of the mesh with three faces from section IV-B. The given face should first be rotated to the plane of the face it is directly connected to, then to the one before it in the path and so on, reverse order until it is finally in the same plane as the base face. This ensures that we don’t have to update the rotations as other rotations happen. The “stack” data structure is perfect for this since it has a “last in first out” property (think of a stack of dirty dishes).
So instead of applying all the rotations corresponding to the grey vertices as we encounter the faces, we store the rotation and the face it is to be applied to in a stack. Once the depth first search has completed exploring all vertices, we actually apply the rotations by popping one at a time from the stack the faces and corresponding rotations to be applied. Below is a visual demonstration of this algorithm going from the Tesseract to the mesh by performing the required sequence of rotations.
And here is a Python implementation of the above algorithm.
Here is a video where this algorithm is applied to the familiar 3-d cube:
When we saw our first 2-d mesh in section III (figure 3), we asked how many there are. And in the absence of an exact answer, we’d like upper and lower bounds that are as tight as possible.
We’ll describe in section VI, a way to generate random meshes starting with one of them. If we then keep only the topologically distinct meshes, we’ll build not only a library of meshes, but also a computational lower bound, which is the distinct number we’ve managed to collect. Any theoretical lower bound will ultimately be superseded by the computational one. So far, the algorithm (I run it once in a while for 10 minutes and add to the mesh collection) has managed to collect about 600 distinct meshes (and this count is always increasing). The current computational lower bound on the number of 2-d meshes of a Tesseract is therefore 600.
For the upper bound, recall the algorithm in section IV-C which generates a valid mesh from a spanning tree of the face graph whenever this is possible (which very often isn’t). And even among the meshes we get this way, there will be versions that are topologically similar to other meshes seen previously. So, the number of spanning trees should be a comfortable upper bound on the number of distinct meshes.
Moreover, since every mesh corresponds to a unique spanning tree (but a spanning tree might not yield a mesh), one way to count the number of meshes (while building a library of them as well) is to loop through all possible spanning trees. For each one, we check if a mesh is possible and if it also happens to be a “topologically novel” one (meaning we haven’t seen any before that its topologically similar to), we save it somewhere.
The problem is that the number of spanning trees turns out to be 10²⁰ (can be obtained by applying Kirchhoff’s matrix tree theorem to the graph in figure-4). So, even if we take a milli second to process a single spanning tree, it’ll take more than the current age of the universe so far to exhaust all of them. The only thing we get from this line of attack is thus a very generous upper bound on the number of meshes. There are ways to improve on this, but we won’t get into them for now, since they still keep the upper bound at astronomically high numbers.
The algorithm in section IV-C will always give us a mesh corresponding to a spanning tree if such a mesh is possible (which often isn’t the case). If we have a way to iterate over spanning trees, we can generate a mesh where possible
As mentioned in the previous section, one way to get a lower bound on the number of distinct meshes is to simply start generating them and eliminating the ones that are topologically the same as a mesh seen before. Such an algorithm will keep “collecting” meshes, a bit like the coupon collectors problem and maintaining a “library” of distinct meshes seen so far. A problem with this approach is that we’ll never know for sure if and when we’ve seen all meshes. When we’re very close to generating all meshes, it’ll become harder and harder to “collect” any more. Towards the end, almost every mesh we randomly draw will have been seen before. And so, if we’ve generated a lot of meshes without running across a new one, it could be because we’ve simply completed our collection or that a few are left and it has just become really hard to see a new one when drawing randomly.
For now, we choose to live with this drawback and simply collect as many meshes as we can. Our algorithm has two parts.
The first starts with a given mesh and generates another valid random mesh from it, that is guaranteed to be different from the previous one. This is done by cutting the edge between two connected faces of the first mesh. This creates two sub-meshes and also two sub-trees (the original spanning tree has been cut in two). Then, we find another two faces (one from the first sub-mesh, one from the second) to “paste” the two sub-trees together and create a new spanning tree. Since the two “sub-trees” are connected again, the property of being able to go from any face to any other face is re-instated. And then, we can use the algorithm in section IV-C to see if this new tree generates a valid mesh. If it doesn’t, we simply generate a new tree and keep going until we find another valid mesh. The mesh is saved to disk as a text file, which is the adjacency list of the corresponding spanning tree.
The second part compares the new mesh with all existing meshes and removes the ones that have been seen before.
These ideas are implemented in the following Python code: https://github.com/ryu577/pyray/blob/master/pyray/shapes/twod/tst_sq_mesh.py. The second part is really the computational bottle neck. The more meshes we collect, the more expensive it becomes to compare a new mesh to all the previous ones. As mentioned, this two-part algorithm can be run in a loop forever until it becomes extremely, extremely hard to find new meshes.
The problem of enumerating the 2-d meshes of a 4-d cube has two hallmarks of the most popular Math problems. It’s easy to explain and frame in a way that almost anyone can understand it. At the same time, it seems that even our most sophisticated tools are falling short of solving it. At a minimum, we can unleash our computing power on this problem and discover close to all the meshes.
_______________________________________________________
If you liked the story, become a referred member 🙂
https://medium.com/@rohitpandey576/membership
[1] Paper 1984 where 3-d meshes are mapped to paired trees (https://unfolding.apperceptual.com).
[2] Martin Gardner’s book from 1966 (“The colossal book of mathematics”: https://www.logic-books.info/sites/default/files/the_colossal_book_of_mathematics.pdf)
[3] MathOverflow post where all distinct 3-d meshes are plotted (https://mathoverflow.net/questions/198722/3d-models-of-the-unfoldings-of-the-hypercube/)
[4] Introduction to algorithms by Cormen et.al.
Denial of responsibility! Techno Blender is an automatic aggregator of the all world’s media. In each content, the hyperlink to the primary source is specified. All trademarks belong to their rightful owners, all materials to their authors. If you are the owner of the content and do not want us to publish your materials, please contact us by email – [email protected]. The content will be deleted within 24 hours.