Bain’s N-cube algorithm

The impulse behind developing and drawing these damned things has more to do with the high “coolness factor” than with making any formal contribution to the body of knowledge we call mathematics. In that sense, I am a failure as a mathematician. I could perhaps try to pawn my work off as art, but, really, I’m not communicating anything other than perhaps some infantile desire to show off. In that sense, I am a failure as an artist. This is one of my hobbies. If you think of some application for this stuff, come up with a new twist, or have any other requests, please let me know.

Van Bain, 18 September 2004

vanirex@msn.com

Downloads

The first N-Cube program I ever wrote.

The second N-Cube program, which also makes *.bmps but is not animated.

A wallpaper of an N-Cube at n=10.

Don’t forget to scan for viruses! You can never be too safe. Source code is unavailable (no biggy, write your own!).

generating and drawing n-cubes: an inductive approach

The hybercube has become a model in an area far different from its origin in astrophysics: parallel processing. Johnsonbaugh, in Discrete Mathematics, 1993, discusses the basic model:

The n-cube has 2 ⁿ processors, n >= 1, which are represented by vertices labeled 0, 1,..., 2ⁿ-1. Each processor has its own local memory. An edge connects two vertices if the binary representation of their labels differs in exactly one bit. If a processors needs to communicate with a nonadjacent processor, the first processors sends a message...it may take several time units for a processor to communicate with a nonadjacent processors (Johnsonbaugh : 311).

The connectivity and node identity of the n-cube are what have been adopted by the processor model, not the spatial features which were originally the focus. There are several methods for drawing n-cubes, but all share a common pitfall: they attempt to maintain as many right angles as possible. In doing so, they sacrifice the simple beauty of the binary relationships between nodes, as well as complicating the graph production methodology.

The following algorithm breaks two unspoken rules of drawing n-cubes: perspective and angularity. Perspective is used by artists, designers, and engineers to fool the mind into seeing three dimensional structures on two dimensional artifacts. Rectilinearity refers to the attempt to maintain as many right angles in the graphs as possible. That system breaks down when dimension increases past three, and since n-cubes are multi-dimensional structures, it's clear perspective drawing fails. By removing the constraint of attempting to show a series of connected squares, focus can shift to discrete mathematics features. In short, it’s not a cube, it's a graph with interesting features. The focus on angular relationships is of value only in helping neophytes move from the familiar to the unfamiliar. Bain’s N-Cube Algorithm for drawing an n-cube extends the algorithm for generating Gray Code sequences discussed in Discrete Mathematics. First the theorem, then the explanation:

Theorem 6.3.6. Let G1 denote the sequence 0, 1. We define G(n) in terms of G(n-1) by the following rules:

(a) Let GR(n-1) denote the sequence G(n-1) in reverse.

(b) Let G'(n-1) denote the sequence obtained by prefixing each member of G(n-1) with 0.

(c) Let G''(n-1) denote the sequence obtained by prefixing each member of GR(n-1) with 1.

(d) Let G(n) be the sequence consisting of G'(n-1) followed by G''(n-1).

Then Gn is a Gray code for every positive integer n (Johnsonbaugh : 335) .

Example 6.3.8

We use Theorem 6.3.6 to construct the Gray code G(3) beginning with G(1).

G(1)	0 1
GR(1)	1 0
G’(1)	00 01
G”(1)	11 10
G(2)	00 01 11 10
GR(2)	10 11 01 00
G’(2)	000 001 011 010
G”(2)	110 111 101 100
G(3)	000 001 011 010 110 111 101 100

(Johnsonbaugh : 336).

Generating a Gray Code bears a direct relationship to generating the nodes of an n-cube. However, Theorem 6.3.6 offers no method for generating edges; the “parallel computing n-cube” definition states every node is connected to another node whose identity varies by only 1 bit. For example, on an n=3 cube, the node 101 would be connected to 001, 110, and 100. The N-Cube Algorithm extends Theorem 6.3.6 to add these edges. It also starts with n=0, rather than n=1.

Initial State (n=0)

Construction Elements

A plane defined by x and y axes.

A point called 'O' for origin.

Another node called 'null' (it has no name right now).

A line called 'R' for reflection line.

Metrics

2 dimensional polar coordinates - (T,D) where T = angle and D = distance from origin.

Preparatory Directions

Place O at the origin (0,0).

Place NULL at (PI,1).

Draw R so that it runs through both O and NULL.

R splits the plan into two sectors; any node whose angle with respect to the origin is:

PI > angle > 0 in the '0' sector,

PI < angle < 2PI in the '1' sector.

Summary of Algorithm

Scale. Divide all node angles by two.

Reflect. Reflect "0 sector" nodes and edges through R.

Connect. Connect each node with its reflection.

Label. Concatenate each node's label with its sector.

Example: Produce n=3

Produce n=1 from n=0

Scale. NULL node's location is (PI,1). It's new location becomes (PI/2,1).
Reflect. NULL node is reflected through R to produce NULL', which is at location (PI *3/2,1). NULL' is in the "1" sector. There are no edges to reflect.
Connect. An edge is produced between NULL and NULL'.
Label. Concatenation for NULL produces 0+NULL = 0, and concatenation for NULL' produces 1+NULL' = 1 ( '+' is Pascal's symbol for string concatenation).

Result.

construction elements,

P 0 at (PI/2,1),

P 1 at (3PI/2,1), and

E 0-1.

Graphic Demonstration of n=1 from n=0

Produce n=2 from n=1

Scale

P 0	PI/2	->	PI/4
P 1	3PI/2	->	3PI/4

Reflect

P 0	->	P 0’	at 7PI/4
P 1	->	P 1’	at 5PI/4
E 0-1	->	E 0’-1’

Connect

-> E 0-0’

-> E 1-1’

Label

0 + 0	->	00
0 + 1	->	01
1 + 1’	->	11
1 + 0’	->	10

Resulting n=2

construction elements,

P 00 at PI /4

P 01 at 3PI/4

P 11 at 5PI/4

P 10 at 7PI/4

E 00-01

E 01-11

E 11-10

E 10-00

Graphic Demonstration of n=2 from n=1

Produce n=3 from n=2

Scale

P 00	PI/4	->	PI/8
P 01	3PI/4	->	3PI/8
P 11	5PI/4	->	5PI/8
P 10	7PI/4	->	7PI/8

Reflect

P 00	->	P 00’	at 15PI/8
P 01	->	P 01’	at 13PI/8
P 11	->	P 11’	at 11PI/8
P 10	->	P 10’	at 9PI/8
E 00-11	->	E 00’-11’
E 01-11	->	E 01’-11’
E 11-10	->	E 11’-10’
E 10-00	->	E 10’-00’

Connect

-> E 00-00’

-> E 01-01’

-> E 11-11’

-> E 10-10’

Label

0 + 00	->	000
0 + 01	->	001
0 + 11	->	011
0 + 10	->	010
1 + 10’	->	110
1 + 11’	->	111
1 + 01’	->	101
1 + 00’	->	100

Resulting n=3

Construction elements,

P 000 at PI/8

P 001 at 3PI/8

P 011 at 5PI/8

P 010 at 7PI/8

P 110 at 9PI/8

P 111 at 11PI/8

P 101 at 13PI/8

P 100 at 15PI/8

E 000 - 001,

E 001 - 011,

E 011 - 010

E 010 - 000

E 100 - 101

E 101 - 111

E 111 - 110

E 110 - 100

E 000 - 100

E 001 - 101

E 011 - 111

E 010 - 110

Graphic Demonstration of n=2 -> n=3

n=3 Final Step

Remove construction elements (O&R).

Without stepping through the algorithm, here are some more n-cubes:

Taking a closer look at each n-cube graph reveals several features. Primarily, the Gray Code sequence always begins with 0 and continues counter-clockwise via the outer edges. Also, it clearly demonstrates that Gray Code sequence is also a Hamiltonian cycle.

Hypercubes continue to stimulate discussion and serve as models for discussion of 4+ dimensional physics, but in astrophysics, those dimensions are of time and space. For those more interested in the n-cube's graph than its shape, Bain’s N-Cube Algorithm better demonstrates the n-cube's true nature.

Bain’s 3D N-Cube Algorithm.

Extending the algorithm to produce a “3-dimensional” n-cube model could be accomplished any number of ways. The method I use produces some very beautifully structed models, where the fractal nature of an algorithm like this begins to really show. By fractal, I mean the repetition of pattern through scale; small parts of the n-cube look like big parts. The algorithm involves a slightly different starting state and one additional step in the N-Cube Algorithm.

Coordinate system: Left-Handed Coordinates, Right-Hand rule.

The left-handed coordinate system extends the familiar x-y two-dimensional system to add a third axis, called the z-axis perpendicular to the other two. If the plane you are reading this information on were the x-y plane, then the positive z-axis would extend away from you, and the negative z-axis would be sticking out at you. This is called the left-hand system because if you form an ‘L’ shape with your left forefinger and thumb, and then make you middle finger stick directly away from the others, all of these digits will be pointing in the positive direction of each axis (x is your left thumb, y is your index finger, and your middle finger is the z-axis).

The right-hand rule refers to how angles are measured. If you were to grab an axis with your right hand and point your thumb in the postive direction, an increase in angle would move in the direction your fingers are curled around the axis, in a counter-clockwise direction. This is the standard for math and computers, but our geographic coordinate system works just the opposite, using the left-hand rule.

POV-Ray uses this system, but all the different combinations of coordinate and angle rules are used in various applications and bodies of knowledge. Regardless of the system, adapting the algorithm is a minor chore (sign changes, etc.).

Algorithm Summary

Scale. Divide all z-axis angles by two.

Reflect. Reflect "0 sector" nodes and edges through the x-z plane.

Connect. Connect each nodes with its reflection.

Rotate. Rotate all nodes around the y-axis by -PI/4 (-90 degrees).

Recalculate Angles. Recalculate Ay and Az from the node’s current x,y,z coordinates.

Label. Concatenate each node's label with its sector.

Initial State.

Same as with original algorithm, but we need three coordinates, two angles and a distance. (Ay,Az,D).

Ay. This is the addition to the coordinate system, and refers to the angle of rotation about the y-axis. A value of 0 is aligned with the positive x-axis.

Az. This is the same angle used in the 2D algorithm, and is the one that gets scaled.

D. This is the unit distance from the origin.

Construction Elements

A left-handed 3-space defined by x,y, and z axes.

A point called 'O' for origin.

A node called 'null'.

A plane called 'R' for “reflection plane” on the x-z axis.

Initial starting point for ‘null’ is the same, at (PI/2,PI/2,1).

Production Notes

Scale. No change. However, please understand this scaling, in rectilinear terms, has no affect on the node’s z value; only the x and y values are affected (the node does not move closer or father away from the x-y plane). My main complaint is that the calculations I currently use fail to produce a perfect cube for n=3, and that’s esthetically displeasing. Perhaps I still want to hang onto equidistance so bad, I just can’t face the truth of it.

Reflection. Instead of reflecting through a line, we are reflecting through a plane.

Connect. No change.

Label. No change.

Rotation. This is not a scaling, but a straight rotation, and is a constant -PI/2 regardless of the node’s current Ay value. I generally do not perform the final rotation because it does not effect the structural relationship of the nodes, and it actually interferes with the rotation animations I make. For example, when my final state is n=8, I do not rotate when producing n=8 from n=7.

Recalculate Angles. Calculate each node’s Ay value from its x and z coordinates. Calculate each node’s Az value from its x and y. Be very careful in this—there are lots of pitfalls. I still have doubts about my implentation, occasionally, and have to blow a few hours figuring it out all over again.