Hypercube

I have came across the problem of generalizing the construction of n-dimensional cubes while working on C++ program hypervision, a vizualizer of higher dimensional objects. In hypervision I wanted to give the user the ability to not only explore 4 dimensional cubes but also any dimensional cubes so it would be important to find a general solution for the construction of n-cubes.

Making a cube is pretty easy, you take two squares and then just connect all the corresponding vertices of each square. Turns out it's the same process for any dimension of cube you want to make. As in, to make a n-dimensional hypercube you take two (n-1)-dimensional hypercubes and connect their vertices together. It was this relationship that made me realize that I could probably find a recursive algorithm that could generalize the problem of creating n-hypercubes so I wouldn't need to write a function for every dimension.

In the text bellow I will refer to a n-dimensional hypercube simply as a n-cube.

Let's look at how to build a 3-cube, aka "the" cube. Also, I will number each vertex as we place them. Each point is represented by it's coordinates, in 3d (x, y, z). Our algorithm must also output the pairs of vertices that have edges between them. It's also ideal if we could build the edges of the cube as we place the points so we don't need to loop over cube twice. For a 3-cube of side-length 2 we can start off with the bottom-most point:

vertex	coords
0	(-1, -1, -1)

edges
none

Now, we need to place our second point. We shall move across the x-axis towards (1, -1, -1). This point and the last one will form the first side of the square at the base of our cube.

vertex	coords
0	(-1 -1, -1)
1	(1, -1, -1)

edges
(1,0)

This is what our current cube looks like, we have added the next vertex and, as promissed, we created the edge needed. This time we can see that the current vertex had an edge with the previous one. Now let's place the third vertex. We shall go back to the original X-value but now we will go up the Y-axis.

vertex	coords
0	(-1, -1, -1)
1	(1, -1, -1)
2	(-1, 1, -1)

edges
(1,0) (2,0)

Okay, as you can see, vertex 2 only has an edge with the vertex 0, this pattern will be important later on. Let's add the fourth vertex and complete the base of our circle.

vertex	coords
0	(-1, -1, -1)
1	(1, -1, -1)
2	(-1, 1, -1)
3	(1, 1, -1)

edges
(1,0) (2,0) (3,1) (3,2)

Vertex number 3 has added two edges, the one before it (3,2) like vertex number 1 did and the one before the one before it (3,1), like vertex number 2 did. It seems like vertex number i will have and edge with vertex i every two vertex. And, vertex i will have an edge with i-2 twice every four times. The pattern is clear when writing the vertex numbers in binary:

vertex	coords
000	(-1, -1, -1)
001	(1, -1, -1)
010	(-1, 1, -1)
011	(1, 1, -1)

edges
(1,0) (2,0) (3,1) (3,2)

Now we can see a beautiful pattern emerge from the cube. The coordinates of each vertex i is i written in binary in reverse order with -1's where the 0's are and, of course, 1's where the 1's are. Even more so, with respect to the edges, when i has the first bit = 1 that is when i has an edge with i-1 and when i has the second bit = 1 it is when i has an edge with i-2.

The intrinsic binary nature of the cube is clear. Like a binomial tree, the nth cube is made with two (n-1)th cubes, this creates the periodicity of the edges and coordinates which correspond to the periodicity of the binary digits of the vertex numbers. In addition, every vertex in a n-cube can be represented with n bits.

The algorithm has revealed itself in it's simpler form, here's my C-style pseudo-code:

struct obj {
    point points[] //list of vertices
    edge edges[] //list of edges
    int dimension //dimension of the object
}

int bit(num, i){
    //returns value of i-th bit of num
    return (num>>i) & 1
}

obj hypercube(obj cube, int current_dimension, float size){
    if (dimension > 0){
        cube = hypercube(cube, current_dimension-1, size)
        cube = hypercube(cube, current_dimension-1, size)
    } else {
        int point_number = cube.points.size()
        point new_point
        for(int i = 0; i < cube.dimension; i++){
            new_point[i] = size * (bit(point_number, i) - 0.5)
            if (bit(point_number, i) == 1){
                int other_point = point_number - (1<<i)
                edge new_edge = {point_number, other_point}
                cube.edges.push_back(new_edge)
            }
        }
        cube.points.push_back(new_point)
    }
    return cube
}
            

And here is the implementation in C++ which was used in my hypervision project.