Message #274

From: Don Hatch <hatch@plunk.org>
Subject: Re: [MC4D] other polychora and polytope permutation puzzles
Date: Thu, 08 Jun 2006 23:19:36 -0700

On Sat, Jun 03, 2006 at 06:39:47PM -0700, Melinda Green wrote:
> Roice Nelson wrote:
> > I had the thought the other day that it would be cool to do a 4D
> > version of the Megaminx. A little wikipedia and web searching
> > revealed that the word ‘polychoron’ is a common (though not standard)
> > word for a 4D ‘polytope’, which is the word for a generalized
> > d-dimension polygon (a 3D polytope is a polyhedron). Also, I found
> > that the 120-cell ( http://en.wikipedia.org/wiki/120-cell) is the
> > polychoron that could be considered the 4D analog of the dodecahedron,
> > which the Megaminx is based on.
> Yep. Don and I have both done a bunch of work visualizing the 120 cell
> and other regular 4D objects when we were in school together in 1985-86.
> In roughly 1992 when we were working on probably our 2nd implementation
> of MC4D, we talked a fair amount about puzzle versions of other
> polytopes. Don began work on a general engine to produce puzzles from
> general 4D polytopes but never finished it. It turns out that not all
> regular polytopes slice up nicely into puzzles. If I recall correctly,
> the good ones in N-D are those in which D faces meet at each vertex.
> Those with more faces result in cuts that generate a bunch of little
> "scrap" cells in addition to the normal ones.

Wow, your memory is good. I didn’t remember that at all,
but it makes sense– try to make a rubik’s-like puzzle out of an octahedron
or icosahedron, it would suck.

> I think that we agree that
> the 120-cell is the most beautiful of the regular 4D polytopes and we
> dreamed about seeing its puzzle version.
> >
> > There is a really cool picture of an exploded 120-cell projected into
> > 3D space about halfway down the page at
> > http://home.inreach.com/rtowle/Polytopes/polytope.html. This
> > is mostly what I was thinking about, though I imagined slightly
> > different projection parameters that would have the closest face
> > hidden like in MC4D.
> I’m fairly sure that that image has the closest face hidden just like in
> MC4D otherwise it would overlap the rest of the figure. IOW, it looks
> like a pretty good projection for a usable puzzle to me. Note that they
> also seem to have removed the next layer of cells which are flattened
> even more than the thin ones you can see edge-on. I suppose they did
> that to let you see deeper inside. You can see the wide, shallow
> indentations where they would nest around the outside. A real 120-cell
> with only the outer face removed would have only 12 outwardly facing
> pentagons in the shape of a dodecahedron.

I think that picture is an orthogonal projection,
showing only the "front" 60 of the 120 cells.

> > I saw a picture having projection parameters I like at
> > http://www.bathsheba.com/math/120cell/, though it isn’t a cool
> > exploded view. The latter is more analogous to how I tried to flatten
> > a 3D dodecahedron into 2D when thinking about this.
> This view seems similar to your 5D puzzle in which the wireframe
> rendering solves a good deal of the crowding problem. Perhaps a puzzle
> version could have a slider that allowed you to quickly hide more or
> fewer layers of cells either by making them invisible or turning them
> into wireframe mode.
> >
> > Maybe the Magic120Cell puzzle would be too much with 120 faces. If
> > they couldn’t realistically be distinguished by colors, stickers might
> > have to be numbered.
> I’m not completely sure about that but we’d have to test it to be
> certain. Perhaps some highlighting tools would help to mitigate the problem.
> > I have seen a Megaminx with only 6 colors which had colors repeated on
> > opposite sides. Maybe doing something like that could help, though it
> > does change the nature of the puzzle (aside: I wonder if repeating
> > colors, but not on opposite sides, could produce a Megaminx that
> > behaved exactly as the 12 colored one, since the 1-colored center
> > pieces can’t change position and the other pieces have multiple colors
> > to help distinguish where they belong. I’ll have to think more on
> > that. If it was the case, maybe colors on a 120cell could even be
> > repeated more than once without changing the puzzle behavior.?.)
> Even if you can do that, it seems like it would make it harder to solve
> than simply allowing 120 unique colors.
> >
> > Anyway, if the 120-cell is over the top, other polychora could make
> > good puzzles.
> Even though the display would be crowded, it may not be as bad as MC5D
> and could have some advantages that might make it easier to solve than
> the 4D cube for the same reasons that the Megaminx seems easier to solve
> than the original Rubik’s cube due to the additional space in which you
> can sequester some parts while working on others.

Yeah, I bet the 120-cell would be a lot easier than the hypercube…
provided you can find where the hell you are trying to put stuff.
I agree, a clever highlighting scheme would be the key to making it feasible
for a human.

And talk about tedious … I think what you’d see is essentially
120 megaminxes, each with 1+12+30+20=63 hyperstickers,
for a total of 120*63=7560 hyperstickers…
compared to only 10*3^4=810 for MagicCube5d,
and 12*3^5=2916 for MagicCube6d.

Another thing to think about– you can use various kinds of
hyperprisms, too. I rendered a bunch of these and they look
like they would be decent puzzles… e.g. a dodecahedral prism,
or a pentagonal-prism-prism– in fact they look just like MagicCube4D
at first glance.
Some of the twists would have to be limited appropriately.

> > The 4-simplex ( http://en.wikipedia.org/wiki/4-simplex) would be the
> > 4D analog of Pyraminx, and would be easier and less screen-crazy than
> > MC4D. That puzzle would also be interesting because as I imagine one
> > projection of it, there would be no center face. There would be 4
> > icosahedrons all pointing towards an empty center. The 5th
> > icosahedron would be the hidden face closest to the viewer (think of
> > the 3D to 2D case of projecting the icosahedron of a Pyraminx to 2D).
> Icosahedral pieces? Is that right? I’d definitely love to try my hand at
> solving this one since I can usually intuit my way to solving the 3D
> version fairly quickly.
> >
> > An interesting thing about these puzzles is that relative to the
> > orthogonal coordinate axes, face rotations can affect all coordinates
> > of a sticker. Just like some face twists on Megaminx can change all 3
> > coordinates of the moved stickers, some face twists on Magic120Cell or
> > Magic4Simplex could change all 4 sticker coordinates. This is unlike
> > the cube puzzles, and it seems this could make the programming more
> > difficult, e.g. in MC4D you can reduce face rotations to 3D rotations
> > by simply not dealing with 1 of the 4 coordinates, but this will no
> > longer be possible. This wasn’t a problem in MC5D either, because we
> > limited rotations to those parallel to coordinate planes and all face
> > rotations only changed 2 coordinate values for stickers. I don’t
> > understand it yet, but apparently 2 quaternions can represent any
> > general 4D rotation (vs. 1 that is required for 3D rotations). What I
> > don’t know is how to interpret the quaternion parameters with a
> > geometric meaning, like the rotation plane and rotation angle. For a
> > 3D rotation, the quaternion that represents it has a direct
> > geometrical way to think about it in terms of an axis of rotation and
> > an angle, but I’m not sure if the 4D case even has a similar
> > geometrical interpretation. If anyone has any information on this, I
> > would appreciate it.<br> > My understanding is that even though quaternions do generalize, the
> property that makes them useful for managing 3D rotations is just a
> quirk that does not generalize. OTOH, arbitrary N-dimensional rotation
> matrices are not terribly difficult to deal with. Essentially all you
> need to do is specify the particular 2D plane in which you want to
> rotate and the amount of rotation you want and you can build the matrix
> directly from that. Don is really good with all of this stuff and his
> vec_h.c program can generate a C macro library with functions for doing
> all of the matrix math in whatever dimension you want.

I haven’t heard of the 2-quaternions-to-represent-abitrary-4D-rotation thing
before, but my guess is it’s the familiar
rotate-followed-by-translate scheme commonly used to express rigid
transformations in euclidean or hyperbolic space
(commonly used internally in hyperbolic
browsers and other programs like Tyler and my hyperbolic tesselations applet).

That is, the first unit quaternion R (the "rotate" part)
would express an arbitrary rotation in the xyz hyperplane,
and the second unit quaternion T (the "translate" part)
specifies the unit coordinates where (0,0,0,1) should go
using the most direct rotation that takes it there
(which feels like a translation).

Actually I’m lying– probably T needs to be the coordinates
of the halfway point on the arc between (0,0,0,1) and where
it’s being taken (since if you interpret it as the fully rotated
image of (0,0,0,1), then T=(0,0,0,-1) would be ambiguous).
Then every T will represent the same orientation as -T,
which is typical for quaternion representations.

To factor an arbitrary 4d rotation matrix into such R,T,
first figure out T (this can be easily extracted
from the last row of the matrix, except when
the last row of the matrix is (0,0,0,-1) in which case I’d have
to think about it more),
then multiply the original matrix by the inverse of T’s matrix,
to get R’s matrix, from which you can get the quaternion R
in the usual way (i.e. look it up in Graphics Gems).

So if you want to work with this R,T representation
instead of matrices, you’d need to figure out three formulas:
1. How to apply the rotation R,T to arbitrary coords (x,y,z,w)
2. Given rotations R0,T0 and R1,T1, find their composition R,T
3. Given a rotation R,T, find its inverse R’,T’
(i.e. R’,T’ such that R,T composed with R’,T’ is the identity).
It would be interesting to see these formulas;
I wonder if they collapse into something nice.

I always prefer to compose from left to right,
since I think that’s a lot less confusing than the alternative.
So
(x,y,z,w) * (R0,T0) * (R1,R1)
would mean first rotate the coords by (R0,T0)
and then rotate the resulting coords by (R1,T1)…
so the composition (R,T) = (R0,T0) * (R1,R1)
would mean the single rotation that does that.

Don