Wythoff constructions of polytopes (A Tutorial)

Discussion of tapertopes, uniform polytopes, and other shapes with flat hypercells.

Wythoff constructions of polytopes (A Tutorial)

Postby pat » Tue Mar 02, 2004 9:05 pm

For my n-dimensional raytracer, I added regular, convex polytopes by implementing them through Wythoff constructions. There are many other ways to construct specific polytopes. But, Wythoff constructions give the most generic way that I've seen.

This is going to take more time to explain than I will have at the moment, so I will break it up into several posts. In this post, I'm just going to give a high-level overview of the process.

By virtue of the fact that all of the polytopes I am generating are convex, it suffices to find the vertexes of the polytope and find the convex hull of that set of vertexes.

By virtue of the fact that the polytopes are regular, their vertexes form a symmetry group. Additionally, their vertexes all lie on the surface of the same hypersphere about the centroid of the polytope.

By virtue of the fact that the polytopes have a finite number of vertexes (faces, edges, etc.), that symmetry group is finite.

In fact, the group of symmetries of a polytope in n dimensions is generated by reflections across n hyperplanes which pass through the centroid of the polytope.

By virtue of the fact that the vertexes form a finitely-generated, finite symmetry group, there exists a Coxeter-Dynkin diagram for the symmetry group.

So, the process of generating a Wythcoff construction of a polytope is this:
  • Describe the Coxeter-Dynkin diagram of the symmetry group
  • Determine the n hyperplanes of the symmetry group
  • Pick an initial vertex
  • Reflect that vertex across all hyperplanes in the symmetry group
  • Repeat the previous step with any vertexes that don't coincide with ones we already knew until we end up generating no new vertexes
  • Determine the convex hull of the vertexes


Point to note: dual polytopes have the same symmetry group, so what you pick for an initial vertex really matters.

I will probably describe each of these steps in separate follow-on replies here.

ps. to alkaline: If you're not interested in having a tutorial here (since it's not really a forum/discussion-type thing), I can move this information to my own website somewhere. Just say the word.
pat
Tetronian
 
Posts: 563
Joined: Tue Dec 02, 2003 5:30 pm
Location: Minneapolis, MN

Describe the Coxeter-Dynkin diagram of the symmetry group

Postby pat » Thu Mar 04, 2004 10:21 pm

To get things started, we're going to have to describe the symmetry group of the polytope we are trying to generate. This is going to be one of our inputs to the process which will determine our hyperplanes for reflection (the other input will be the inital vertex that we'll reflect around to get the other vertexes).

All finitely-generated, finite symmetry groups can be described by a Coxeter-Dynkin diagram. So, what is a Coxeter-Dynkin diagram?

For our purposes, it is conventient to think of a Coxeter-Dynkin diagram as a graph with the edges labelled by an integer larger than one. Each vertex in the graph will represent one of our hyperplanes. The label on each edge will represent the angle between the two hyperplanes in a very particular way.

Suppose we have two perpendicular planes in three-space and a point equidistant from the two planes (but not on them). Let's alternately reflect the point across one plane, then the other. How long does it take to get back to our original point? The answer is: 4 reflections. That means, we had to do the operation reflect by plane one followed by plane 2 two times. Thus, we'll label the edge between the vertexes that represent these planes with a 2. Conveniently, this also happens to mean that the angle between the planes is <sup>?</sup>/<sub>2</sub>.

Let's do the same thing now with the planes at an angle <sup>?</sup>/<sub>k</sub>. We'll find that we have to do the operation reflect by plane one followed by plane 2 a total of k times to get the vertex back to where we it started. We'll label that edge k.

We label all of the graph-edges this way based upon the angle between the hyperplanes represented by the endpoints of the graph-edge. Now, you might be wondering, what if k is not an integer. Well, if k is irrational, then the point will never make it back to where it started. If k is rational, it turns out, you can find an integer that covers the same points, but it's not immediately coming to me at the moment about how one shows that.

By convention, in Coxeter-Dynkin diagrams, edges labelled '2' are omitted altogether and edges labelled '3' are left unlabelled.

For example, two hyperplanes which are perpendicular are represented
by the Coxeter-Dynkin diagram:
<pre>* *</pre>
Two hyperplanes which form a 60-degree angle (<sup>?</sup>/<sub>3</sub>) is:
<pre>*-----*</pre>
And, two hyperplanes which form a 45-degree angle (<sup>?</sup>/<sub>4</sub>) is:
<pre>*--4--*</pre>

It shouldn't come as a surprise then that the symmetry group of an n-sided polygon is:
<pre>*--n--*</pre>
If you take a point equidistant between the two planes and reflect it across each alternately. You'll get back to where you started after n pairs of reflections having left a trail of n points. Take the convex hull of these, and you've got an n-gon.

There are a variety of restrictions on what Coxeter-Dynkin diagrams can form polytopes. I don't know of any simple way to describe those restrictions. But, if you just made a random graph and randomly labelled its edges, there's a good chance you'd end up with an infinite group.

That said, the standard polytopes have relatively easy Coxeter-Dynkin diagrams. I should point out that these diagrams aren't unique. I've used the standard representations below. Isomorphic diagrams imply identical symmetry groups. But, non-isomorphic diagrams don't necessarily imply differing symmetry groups (because the diagram depends on which generators one picks).

The triangle:
<pre>*-----*</pre>
The tetrahedron:
<pre>*-----*-----*</pre>
The 4-d simplex:
<pre>*-----*-----*-----*</pre>
And, you can see where this is going.... just add another segment on for each dimension. This sequence continues indefinitely.

The square:
<pre>*--4--*</pre>
The cube (and the octahedron):
<pre>*--4--*-----*</pre>
The hypercube (and the hyperoctahedron):
<pre>*--4--*-----*-----*</pre>
The 5-d cube (and the 5-d octahedron)
<pre>*--4--*-----*-----*-----*</pre>
And, you can see where that is going.... just add another segment on for each dimension. This sequence continues indefinitely

The pentagon:
<pre>*--5--*</pre>
The dodecahedron and the icosahedron:
<pre>*--5--*-----*</pre>
The 120-cell and the 600-cell:
<pre>*--5--*-----*-----*</pre>
And, actually, this sequence stops there for some reason. If you add another segment, you end up with two planes coinciding rather than branching out in a new dimension.

I'm pretty sure, for any of the above, you can make it into a prism of the next higher dimension (an extrusion of its current shape) by adding a disconnected point. But, I'm not 100% sure of that.

The only one we've missed that works out is the 24-cell:
<pre>*-----*--4--*-----*</pre>

For my ray-tracer, I chose to represent the Coxeter-Dynkin diagram as the incidence matrix of the graph. Since it's right here, I'll show you then how the 24-cell would be represented in my raytracer. (Ignore the diagonal elements for now).
<pre>matrix [4]<
[4]< 1, 3, 2, 2 >,
[4]< 3, 0, 4, 2 >,
[4]< 2, 4, 0, 3 >,
[4]< 2, 2, 3, 0 >
>;</pre>
For convenience, I assume that any off-diagonal element less-than two is two and I take the maximum of m<sub>ij</sub> and m<sub>ji</sub> to be both m<sub>ij</sub> and m<sub>ji</sub>. That way, the above matrix could really be represented like this and my raytracer would fix it to the above on input:
<pre>matrix [4]<
[1]< 1 >,
[1]< 3 >,
[2]< 0, 4 >,
[3]< 0, 0, 3 >
>;</pre>
pat
Tetronian
 
Posts: 563
Joined: Tue Dec 02, 2003 5:30 pm
Location: Minneapolis, MN


Return to Other Polytopes

Who is online

Users browsing this forum: No registered users and 11 guests