Factoring coordinates

Discuss interdimensional programming, Java applets and so forth.

Factoring coordinates

Postby quickfur » Thu Sep 08, 2011 4:04 am

Alright, I'm feeling generous today, so I'm going to share with y'all how I generated those 22 sets of coordinates for the bitruncated 120-cell. Well, for any set of coordinates, really.

First of all, let's be precise about what exactly we want to do here. Let's say you just figured out a Really Cool Way to compute coordinates for, oh, the omnitruncated E8 polytope, say (I'm just making that up). Now you want to share your great findings with the world. But there's one problem: this thing, it turns out, this monster has like 10000 vertices, and posting 10000 coordinates on your homepage isn't exactly the most readable thing to do. But you know that you can factor these coordinates in nice permutation sets, like Wendy's apacs and epacs operators (aka "all permutations of coordinates, all changes of sign", and "even permutations of coordinates, all changes of sign", respectively). The only problem is, there are too many coordinates to factor by hand (well, there are too many to recognize just by looking, for starters). So how do you go about doing that?

There are probably many solutions to this problem; here's my method.

Partition the vectors into candidate permutations sets

First, you want to group the coordinates in potential permutation sets. For example, if your coordinates include <1,2,3,4,5>, <5,4,3,2,1>, <2,3,4,5,6> and <6,5,4,3,2>, then you'll want to group the first two coordinates into a group, and the second two coordinates into another group, because <5,4,3,2,1> is a permutation of <1,2,3,4,5> but <2,3,4,5,6> is not. How you tell if something belongs in the same group? Easy: just sort the coordinates and compare them. For example, <5,4,3,2,1> sorted becomes <1,2,3,4,5>, so you know it belongs to the same group as <1,2,3,4,5>.

Now, in the real world, things aren't quite this simple. For one thing, polytopes tend to have negative coordinates too (all changes of sign, remember?). So you might have among your coordinates, say, <3,2,-4,1,-5>. You want to put this in the same group as <1,2,3,4,5>, because eventually you want to compare members of the same group to see if you can factor their signs. So when you do the coordinate sort, you want to ignore the sign.

Sign-factoring

OK, so now you divided your coordinates into potential permutation sets. Now what? The next step, at least the way I chose to do it, is to factor the sign. This is easy: we look for two coordinates of the form <A,B,C,D,E> and <A,B,C,D,-E>, and combine them into <A,B,C,D,±E>. That is to say, find a pair in your permutation set whose coordinates are all identical except for one, which differ only in sign. In order to do this, you want to sort within your permutation set so that vectors with identical coordinates up to change of sign are sorted together. (I.e., you want <1,2,3,4,5> and <1,2,3,4,-5> to appear together, and <2,3,4,5,1> to appear separately). This can be accomplished by a custom vector comparison function that you use to sort coordinates, so that as you sort input coordinates in the first step, they are also put into the right order within each permutation set (to save the cost of having to do another sort within each set).

Now, one trick here is that you want to be able to represent the ± as a distinct kind of sign in your vector representation, so that after you have sign-factored four coordinates, <1,2,3,4,±5> and <1,2,3,-4,±5>, you want to be able to detect that the last coordinate of both factored coordinates are the same (i.e. ±5), so that you can continue to factor these two into <1,2,3,±4,±5>. So a simple floating-point representation is not good enough; you must use an extended number representation that admits ± as a distinct "sign". Also, if you're working with floating-point input, it's a good idea to define a custom equality operator that considers two numbers equal if they are within a small number, EPSILON, of each other. The reason is that polytopes tend to have coordinates like <1,0,0,0> and <0,1,0,0>, and when you do permutation factoring, you don't want floating-point roundoff to treat 0.0000000000001 and 0.00000000000002 as different numbers.

So anyway, you just repeatedly sign-factor within a permutation set until there are no more factorable pairs to be found. You can probably apply some clever algorithm here so that you don't end up with an O(n2) algorithm that scans the set many times over. For me, I used C++ STL's multimap container with a custom comparison function that always puts vectors with ± at the front of the set (and sorts them in such a way that vectors that differ in sign in exactly one coordinate, the kind that can be factored, are very likely to appear next to each other). This way, it's quite easy to find factorable pairs of vectors.

Factoring permutations

You do this until the permutation set can no longer be sign-factored, at which point you have something like this in your permutation set: <±1, ±2, ±3>, <±2, ±3, ±1>, <±3, ±1, ±2>. Now you are ready to factor the permutation. Your custom sorting function should be written in such a way that elements in your permutation set appear in lexicographical order. Why? Because there is an excellent known algorithm for enumerating permutations in lexicographical order. What we do at this stage is very simple: assume the set is in lexicographical order, then make a copy of the first vector in the set, and start enumerating its permutations. As you do so, check the remaining vectors in sequence; if they exactly match the enumerated permutations, then you can replace the entire set with either AP or EP (All Permutations, or Even Permutations). So for example, a set like <0,0,±1>, <0,±1,0>, <±1,0,0> can be replaced by ap<0,0,±1>. Then, if every coordinate has a ±, you can remove all the ±'s and write apacs<0,0,1>.

So how do you enumerate all permutations and even permutations in lexicographical order? This is how.

If you're clever, you can combine AP and EP recognition into a single pass: modify the algorithm described in the above page, so that instead of only returning even permutations, it returns all permutations but also tells you whether each permutation is even or odd. Then as you enumerate, if all the odd permutations are missing then you know it's an EP; if all permutations are present then it's an AP.

Repeat this for each permutation set and you got a nicely-factored form for your coordinates that you can post on your homepage without ending up with a 1-pixel scrollbar. :) For example, using this algorithm I managed to reduce the 3600 vertices of the bitruncated 120-cell into 22 apacs/epacs expressions. Otherwise, the coordinates wouldn't fit on the page!

Hope y'all found this helpful.

P.S. Of course, permutation factoring is just one part of the story... the other part is how to get nice coordinates like φ and φ2 instead of just 1.6180339887 and 2.6180339887 (or ugly-looking things like (1+sqrt(5))/2 and (3+sqrt(5))/2 if you're using something like mathcad). That belongs in another post, which I'll share if I continue feeling nice and generous. ;)
quickfur
Pentonian
 
Posts: 2482
Joined: Thu Sep 02, 2004 11:20 pm
Location: The Great White North

Re: Factoring coordinates

Postby Mrrl » Thu Sep 08, 2011 4:52 am

Here is description of bitruncated 120-cell that I use in my program:

Dim 4
Faces 4.236068,1,1,1 4.3777088,0,0,0
Group 0,4.472136,-7.236068,0/0,5.854102,-9.472136,8.09017 0,0,1,0/0,0,0,1 -0.618034,1.618034,1,0/0,0,0,1

Not very long :)

(actually there are 8 more lines that describe cutting planes and cell twists for the puzzle, but they do nothing with the body shape).
Mrrl
Trionian
 
Posts: 165
Joined: Sun May 29, 2011 7:37 am

Re: Factoring coordinates

Postby quickfur » Thu Sep 08, 2011 5:00 am

Hey are you the guy who wrote the 7D twisty puzzle program??
quickfur
Pentonian
 
Posts: 2482
Joined: Thu Sep 02, 2004 11:20 pm
Location: The Great White North

Re: Factoring coordinates

Postby quickfur » Thu Sep 08, 2011 5:02 am

Anyway, my approach is more primitive, i suppose, i'm actually explicitly computing the entire face lattice of the polytope and storing it in the polytope definition file.
quickfur
Pentonian
 
Posts: 2482
Joined: Thu Sep 02, 2004 11:20 pm
Location: The Great White North

Re: Factoring coordinates

Postby wendy » Thu Sep 08, 2011 8:16 am

We also handle odd permutations as well A / E / O / + all / even / odd / and P, C permutations, change of sign.

In any case, the coordinates for various figures are found by a means of projection into lattices and lattice-stations. This is considerably easier than dealing with the polytope direct. Let's look at 't-basic' or A_n, for example.

The basic form of t-basic is a 60-degree rhombic tile, divided by another set of planes, perpendicular to the rhombs. This divides the rhombotopes into the various kinds of simplex and n-rectate of the simplex. In 3d, this divides the 60-rhombohedron into tetrahedron, octahedron, tetrahedron.

The centres of the cells and the vertices are 'stations', where one could freely put the cell-vertex without destroying the symmetry of the figure. In the dynkin-graph, these correspond to the separate vertices of the polygon that forms this figure.

Where t-basic in say 3 dimensions represents a slice of the cubic in 4d, the section being along the diagonal of the tesseract. Normally, the plane sum(x)=0. But one can take sum(x)=1, 2, 3, to get the same point falling in different cells of the tiling. This equates to moving the cells around the vertex.

Let's now look at the basic tilings.

We imagine now that t-basic is not points but a layer of spheres. We can place more like rows of spheres on these, to get various tiling. In 3d, this would be a triangular tiling {3,6} vertices.

If new layers advance 1, 2, 3 stations around the ring, from the previous, then we get the corresponding t-basic, semi-cubic and gosset tilings of that dimension. (gosset-tilings go down as far as 2d, prehaps lower). If one alternates +1 to -1, or +2 to -2, then one gets a kind of 'close pack' in various dimensions. These have the same packing efficiency as going straight ahead, but are not 'lattices' per se.

Here we see Gosset's 8D lattice, packed against a simplex-tiling lattice. In the first, we see it in classical 3-step form. (for a base of 9, there is no height, and the three layers of spheres fit smugly into the same height!). Every second layer corresponds to a semi-cubic, which leads to the classical heights. Every third layer corresponds to A8, or the 8D t-basic.

The next trick is to supply distances for this.

The edge2 is taken as (2m) where the base goes from 0 to m-1. Here m=8. The distances between stations is found by, eg (c)(m-c), where 1*7, 2*6, 3*5, 4*4 or 7, 12, 15, 16. The layer heights then are expressed as hr² where h is some constant, and c is the row number. We have for the t-basic, h=16-7 = 9, for q-cubic, h=16-12 = 4, and for gosset, h=16-15 = 1. There are three edge-sums equal to 16 here: 1r 3c , or 2r 2c, or 3r 1c. These can be seen in the diagram.

One then draws spheres in here to the desired size, noting that these correspond to the cells in the vertex-figure.

Code: Select all
   Gosset's 8D lattice, by t-axis.


    x  o  o  o  o  o  o  o  t   g  64
    o  o  o  o  o  x  o  o      g   49
    o  o  x  o  o  o  o  o  t q g  36
    o  o  o  o  o  o  o  x      g   25
    o  o  o  o  x  o  o  o    q g  16
    o  x  o  o  o  o  o  o  t   g   9
    o  o  o  o  o  o  x  o    q g   4
    o  o  o  x  o  o  o  o      g    1
    x  o  o  o  o  o  o  o  t q g   0
    0  1  2  3  4  5  6  7


    o  o  x  o  o  o  x  o    36
    x  o  o  o  x  o  o  o   16
    o  o  x  o  o  o  x  o    4
    x  o  o  o  x  o  o  o    1
    0  1  2  3  4  5  6  7



Another cute trick in the simplex, is that there is a strong modulus principle applies. Number the nodes from 1 to m-1. eg (1)---(2)---(3)---(4). When the vertices are marked, add these numbers up (eg x3o3x3o = 1+3 = 4), and take these modulo m. The figure then would fall when one moves the vertex four left in the lattice. The first polytope in the 0-layer is x3o3o3x, eg 1+4. Here, 2+3 also works, so we find this too, o3x3x3o. When rows are integers > 1 then one adds it in as a square, eg 1s0s0s3 (meaning x3o3o3x where the second edge is three times larger than the first), gives 1+0+0+9*4 = 37 = 2.
The dream you dream alone is only a dream
the dream we dream together is reality.
User avatar
wendy
Pentonian
 
Posts: 1811
Joined: Tue Jan 18, 2005 12:42 pm
Location: Brisbane, Australia

Re: Factoring coordinates

Postby Mrrl » Thu Sep 08, 2011 12:28 pm

quickfur wrote:Hey are you the guy who wrote the 7D twisty puzzle program??

Yes, it was me...
Mrrl
Trionian
 
Posts: 165
Joined: Sun May 29, 2011 7:37 am

Re: Factoring coordinates

Postby quickfur » Thu Sep 08, 2011 1:38 pm

Mrrl wrote:
quickfur wrote:Hey are you the guy who wrote the 7D twisty puzzle program??

Yes, it was me...

Cool!! I'm a twisty puzzle fan too, although i haven't actually played around very much with higher-dimensional puzzles (I dabbled with magic cube 4D a little before, but not enough to actually solve it). Something i've always wanted to try was a deep-cut 4D puzzle, like a bisected 120-cell or something similar. I suspect it would be insanely difficult, though. :)
quickfur
Pentonian
 
Posts: 2482
Joined: Thu Sep 02, 2004 11:20 pm
Location: The Great White North

Re: Factoring coordinates

Postby Mrrl » Thu Sep 08, 2011 6:28 pm

It was easy enough to build bisected 120-cell with cutting planes parallel to cells. It has 14400 pieces, all of them are 1-color. So solving may be not very difficult, just long enough. Program has powerful macro, setup and piece-finding options, that takes large part of work from the solver.
I added some more half-cut puzzles: 3 variants of tesseract (vertex-, edge- and ridge-centered rotation axes), one 16-cell and one 24-cell (both with cell-centered axes).
Program is here: http://games.groups.yahoo.com/group/4D_ ... /MPUlt.zip , so you may try these puzzles :)
Mrrl
Trionian
 
Posts: 165
Joined: Sun May 29, 2011 7:37 am

Re: Factoring coordinates

Postby quickfur » Fri Sep 09, 2011 2:45 am

Hmph, the link requires a yahoo account, but I don't have one (and don't feel like getting one). :(
quickfur
Pentonian
 
Posts: 2482
Joined: Thu Sep 02, 2004 11:20 pm
Location: The Great White North

Re: Factoring coordinates

Postby Mrrl » Fri Sep 09, 2011 3:21 am

Okay, there is alternative link: http://astr73.narod.ru/MPUlt/MPUlt.zip . But it may require something else (like find a name of the file inside the Russian text and click it).
Mrrl
Trionian
 
Posts: 165
Joined: Sun May 29, 2011 7:37 am

Re: Factoring coordinates

Postby quickfur » Fri Sep 09, 2011 4:02 am

I happen to be learning Russian, so that was no problem for me. :) Thanks!!
quickfur
Pentonian
 
Posts: 2482
Joined: Thu Sep 02, 2004 11:20 pm
Location: The Great White North

Re: Factoring coordinates

Postby quickfur » Fri Sep 09, 2011 4:04 am

P.S. Although, I'm a linux user so i'll have to try running the game on my wife's laptop some other time. Do you happen to have a linux version handy?
quickfur
Pentonian
 
Posts: 2482
Joined: Thu Sep 02, 2004 11:20 pm
Location: The Great White North

Re: Factoring coordinates

Postby Mrrl » Fri Sep 09, 2011 5:22 am

I use Microsoft DirectX for visualization, so there is no Linux, MacOS or Android versions available now... Only Windows. Sorry...
Mrrl
Trionian
 
Posts: 165
Joined: Sun May 29, 2011 7:37 am

Re: Factoring coordinates

Postby quickfur » Fri Sep 09, 2011 2:43 pm

Hmm maybe i should write a linux version. Or a cross-platform version using OpenGL or something.

Although i doubt i have the time to actually do it... :(
quickfur
Pentonian
 
Posts: 2482
Joined: Thu Sep 02, 2004 11:20 pm
Location: The Great White North


Return to Programming

Who is online

Users browsing this forum: No registered users and 1 guest

cron