n-cross tilings of n-space

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

n-cross tilings of n-space

Postby quickfur » Wed Dec 18, 2013 12:04 am

I'm not sure where to post this, but I ran into an interesting programming problem recently, that is somehow related to higher-dimensional geometry. :)

Basically, I'm trying to design an efficient storage scheme for a dense set of points (vectors with integer coordinates) in an n-dimensional state space of some problem that the program is trying to solve. (Oh btw, I'm using "dense" in the programming sense of having many adjacent points, not in the mathematical sense of having a point between every pair of points.) Initially, I considered the usual partitioning of n-space into n-cubes, with each n-cube serving as a "bucket" to contain some set of points. The problem with this approach is that when the set is dense, the average number of points per bucket is kn, which quickly becomes unmanageable as n grows large. Furthermore, upon closer investigation, in each iteration of my algorithm, it actually mostly only cares about points that differ only in a small number of coordinates, so a bucket shaped like an n-cube will actually contain mostly irrelevant points, because in high dimensions, most of the n-cube's bulk is concentrated near its vertices! Instead, a more ideal shape for my buckets is closer to the n-cross, perhaps some manner of truncated n-cross -- basically, the set of points around some given reference point P that differ only in a small number of coordinates from P. Since an n-cross only has 2n vertices, and truncated n-crosses only have k*n vertices for some small constant k, this is far more manageable from a storage efficiency POV -- only O(n) space complexity, as opposed to O(k^n) complexity!

This led me to consider how to partition n-space into buckets of n-cross-like facets. In the ideal case, the partitioning should be facet-transitive (makes the code more manageable if we only have to deal with one shape of buckets). So we're basically dealing with some kind of tiling of n-space with n-crosses (or some kind of n-cross truncates). But I'm guessing probably there's no such partitioning that's facet-transitive, so I'm willing to settle for a uniform tiling instead, or some kind of tiling that requires only 2 or 3 different facets (preferably only 2), and preferably all the facets will have relatively small n-bulk (i.e., not exponential like the n-cube).

I tried searching online but I didn't find any tilings involving the n-cross or truncated n-crosses. What are the known tilings involving n-crosses or low-order n-cross truncates? Are there any good candidates for my program?
quickfur
Pentonian
 
Posts: 2935
Joined: Thu Sep 02, 2004 11:20 pm
Location: The Great White North

Re: n-cross tilings of n-space

Postby quickfur » Wed Dec 18, 2013 3:27 am

Update: After some thought, I'm now considering using the omnitruncated n-simplex tiling. The omnitruncated n-simplex is just the permutohedron, which has some interesting properties, including having nice integral coordinates in (n+1)-space (i.e., all permutations of the integers from 0 to n). Since it tiles space, it gives a nice facet-transitive tiling, which will simplify the coding a lot. Its translation symmetry group also has nice integral properties, which is very good news, because then I don't have to deal with floating-point issues and complex (slow) computations. Being based on the n-simplex, I'm also expecting that its volume should be significantly smaller than that of a commensurate n-cube, so it should have nicer disk space usage characteristics.

Some open questions are:

1) How well does the shape of an omnitruncated n-simplex approximate the n-cross, since the most ideal partitioning is with n-cross facets (since it represents the most likely region where the algorithm would visit consecutively). IOW, is it close enough that it will have significant overlap with the region of most likely subsequent visits, and only a small portion of "wasted" space (regions unlikely to be visited by the algorithm in the near future)?

2) How to map n-space coordinates to (n+1)-space coordinates to take advantage of the integer coordinates of the tiling in (n+1)-space? How to determine which facet a given point falls into (equivalent to factoring a given n-D point in terms of the basis vectors of the tiling's translation group)?

3) What is the ratio of omnitruncated n-simplex volume to n-cube volume? Is the ratio small enough to make a significant improvement over using the latter (which is much easier to code because it's trivial to factor coordinates in terms of coordinate axes basis vectors)?
quickfur
Pentonian
 
Posts: 2935
Joined: Thu Sep 02, 2004 11:20 pm
Location: The Great White North

Re: n-cross tilings of n-space

Postby wendy » Wed Dec 18, 2013 7:13 am

The omnitruncate tiling hight 'Hamilton tiling', corresponds to all nodes marked on a ring. It has a fairly easy derivation. It's the most efficient cell if one wants to cover space with equal-size disks (including intersections). It has (N+1)! vertices per cell, of which N+1 are shared at a vertex.

The alternate tiling ye might consider are things like the general N-dimensional reflex of the series through the hexagon and rhombic dodecahedron. It represents the section outline of an (N+1)-cube vertex-first, or the voronii cells of points x_0 to x_n, where sum_i(x_i)=0. The cells have (n)(n+1) faces (all oblate rhombotopes), and of course 2^(n+1)-2 vertices. The packing efficiency is a cell that holds a sphere of diameter sqrt(2) has a volume of sqrt(n+1), which is the most efficient to three dimensions, but there are better instances in higher ones.

The cross-polytope occurs as a dominate feature in 3, 4, and 8 dimensions, and one can usually find quite efficient examples of it in most other dimensions. The twelve-dimensional instance, formed with cells centred on the third moment of the {3,4,3}, has an efficiency of 2, while the most efficient tiling in that dimension is 2.370 (the Todd-Coxeter tiling). The way you construct this, is to note that {3,3,4,3} can sit on the symmetry E33A (ie a point and four radial branches), in four different ways. Call these 0,1,2,3. Now you take the second and third power of these, and you put cells centred on points as long as the sum is a multiple of four, eg 0,0,0 and 1,2,1, and 3,3,2 are all valid.
The dream you dream alone is only a dream
the dream we dream together is reality.

\ ( \(\LaTeX\ \) \ ) [no spaces] at https://greasyfork.org/en/users/188714-wendy-krieger
User avatar
wendy
Pentonian
 
Posts: 2014
Joined: Tue Jan 18, 2005 12:42 pm
Location: Brisbane, Australia

Re: n-cross tilings of n-space

Postby quickfur » Wed Dec 18, 2013 4:20 pm

wendy wrote:The omnitruncate tiling hight 'Hamilton tiling', corresponds to all nodes marked on a ring. It has a fairly easy derivation. It's the most efficient cell if one wants to cover space with equal-size disks (including intersections). It has (N+1)! vertices per cell, of which N+1 are shared at a vertex.

The alternate tiling ye might consider are things like the general N-dimensional reflex of the series through the hexagon and rhombic dodecahedron. It represents the section outline of an (N+1)-cube vertex-first, or the voronii cells of points x_0 to x_n, where sum_i(x_i)=0. The cells have (n)(n+1) faces (all oblate rhombotopes), and of course 2^(n+1)-2 vertices. The packing efficiency is a cell that holds a sphere of diameter sqrt(2) has a volume of sqrt(n+1), which is the most efficient to three dimensions, but there are better instances in higher ones.

I'm not really concerned about the exact number of vertices or the packing efficiency; the most important features to me are:

  • It should be easy to determine, given any vector v, which cell v falls in. (If it falls on the boundary between two or more cells, an arbitrary judgment call can be made to decide between them, as long as it is consistent for the same v.) Preferably, this determination should be possible using only simple integer arithmetic on the Cartesian coordinates of v. It should be relatively easy to assign a unique label to each cell, so that this label can be used as an index to the storage location of the cell on disk.
  • As much as possible, each cell should include vectors with the smallest Manhattan distance from its center, and exclude most vectors with large Manhattan distances.
  • It should be easily generalized to any number of dimensions, so tilings that only occur in specific dimensions are not interesting (mainly because I don't get to control how many dimensions there are -- that's determined by the input data).
quickfur
Pentonian
 
Posts: 2935
Joined: Thu Sep 02, 2004 11:20 pm
Location: The Great White North

Re: n-cross tilings of n-space

Postby quickfur » Wed Dec 18, 2013 7:44 pm

Upon further thoughts, I'm having reservations about the permutahedron tiling of n-space. The problem is that in order for it to work, I must transform my n-vectors into (n+1)-vectors via a non-trivial rotation that introduces irrational numbers into the coordinates. This basically fails one of my criteria for tilings, because I'll have to cope with floating-point arithmetic and their associated roundoff errors and slowness. Also, in order for the resulting cells to be "close enough" to the anticipated n-cross access patterns of my program, I have to apply a more complex rotation so that the points map to (n+1) dimensions in a nicer orientation -- so it's not just requiring floating-point now, but doing *complex* computations with floating-point.

I'm now turning back to n-cube symmetry tilings, and seriously considering some truncated form of the {4,3,3,..,3,4} n-cubic tessellation. My original desire to move away from pure {4,3,...3,4} is because the n-cube covers far too much n-bulk, most of which will probably not be needed immediately. But now I'm thinking, if I take some manner of truncation of this tessellation, say for simplicity's sake we take the rectified {4,3,...,3,4} tiling, then the cells would be n-crosses (good) and rectified n-cubes. Rectified n-cubes still has rather large volume, but when n is large, most of the n-cube's volume, which is concentrated around its vertices, should have been cut off by the rectification process and redistributed into the 2^n n-crosses that surround each of the rectified n-cubes. The n-crosses would then be the ideal shapes for my cache, since they will contain the most likely candidates for subsequent traversal, and the rectified n-cubes, while not optimal, should be much better than straight-up n-cubes, since the amount of "wasted" space should be smaller.

Furthermore, the major advantage of tilings based on {4,3,...3,4} is that determining which cell a given point belongs to is very easy, and very fast: just simple integer modular arithmetic. No nasty square roots or any of that stuff, that plague n-simplex based tilings.

Of course, the rectified {4,3,...,3,4} is just a first approximation at the ideal tiling. I'm thinking that the mesotruncated {4,3,...3,4} should give the most balanced distribution of volumes between different cell types. Now, I haven't fully thought this through yet, but it would appear that the mesotruncate of {4,3,...,3,4} should always be a facet-transitive uniform tiling of n-space? Is that correct? If so, it may be just the ticket I need. :)

P.S. in case it's not clear what I mean by "mesotruncate", it's basically the tiling with the CD diagram o4oo...oxo...oo4o in odd dimensions, and o4oo...oxxo...oo4o in even dimensions. Basically, it's the midpoint in the series of uniform truncations between x4oo...o4o and its dual.

P.S.S. I just realized that the mesotruncated {4,3,...3,4} is always be facet-transitive, because {4,3,...3,4} is self-dual. Hooray! In fact, the mesotruncated {4,3,3,4} coincides with the tiling of 3-space with the omnitruncated tetrahedron (aka truncated octahedron), but has an orientation that's much easier to deal with using integer arithmetic. So that's a very good sign; it's just the kind of cell shape I need. Of course, the omnitruncated n-simplex tiling series diverges after 3D, but that doesn't matter, since the mesotruncated {4,3,...,3,4} is much better suited for my purposes. Now, I just have to figure out how to determine facet membership of any given vector v, and I'll be all ready to go!
quickfur
Pentonian
 
Posts: 2935
Joined: Thu Sep 02, 2004 11:20 pm
Location: The Great White North

Re: n-cross tilings of n-space

Postby quickfur » Thu Dec 19, 2013 3:31 am

OK, so I'm thinking about how to determine cell membership in the mesotruncated {4,3,...,3,4} lattice in a simple way, and I think I've figured it out, but I just need someone to confirm whether or not my intuition is correct.

Say you have a point X = (x1,x2,x3,...xn). First, find out which n-cube cell it lies in, in the n-cube lattice that the mesotruncate is derived from. This is done by simple modular arithmetic: suppose the edge length of the n-cube is E, then we just compute floor(xi / E) for 1≤i≤n, and construct Y = (floor(x1 / E), floor(x2 / E), ..., floor(xn / E)). Then Y is an integer vector that gives us the coordinates of the n-cube in the n-cube lattice that contains X. The residual vector Z = (x1 mod E, x2 mod E, ...) = (z1, z2, ... zn), where x mod y denotes the remainder of x when divided by y with integer division, then gives the relative location of P within the n-cube cell. Thus far, this is the usual process for determining membership in an n-cube lattice.

But suppose we add a subsequent step. Let C=(c1,c2,...cn) be the nearest vertex of the n-cube from Z. Let d be the sum of the absolute differences in coordinate between C and Z. That is, d = |c1 - z1| + |c2 - z2| + ... + |cn - zn|. Suppose we say that if d < k, for some fixed k, then we paint X black, otherwise we paint X white. Now consider the pattern produced if we apply the above process to all points in n-space. If k < E/2, then what we get is what's effectively a truncated n-cube lattice, with black n-cross cells, and white truncated n-cube cells. As we increase k, the n-cross cells will grow larger. When k=E/2, we obtain the rectified {4,3,...,3,4} lattice. At this point, the original n-cube cells will have become rectified n-cubes. If k continues to grow past that point, then the n-crosses will start to merge into each other, which effectively begins to truncate them. So basically, what's happening is that k is equivalent to the truncation depth of the n-cube lattice, and each value of k gives rise to some truncate of the {4,3,...,3,4} lattice.

Now let B=(b1,b2,...bn) = (E/2, E/2, E/2, ...), that is, B is the center of the n-cube cell. Let b = |b1 - z1| + |b2 - z2| + ... + |bn - zn|. Then b is the Manhattan distance of Z from B, just as d is the Manhattan distance of Z from C. Suppose we now paint X black if d < b, and white if d > b. This means that points that are closer to C (using the Manhattan metric) are painted black, and points that are closer to the center of the n-cube cell are painted white. What would the resulting pattern be? Clearly, it's some truncation of the n-cube lattice. But which one?

My conjecture is that it's the mesotruncated {4,3,...,3,4}, because the points with d=b are precisely those points that are equidistant to the n-cube's corner and center (under the Manhattan metric), implying that the shape of the truncated n-cube must be the same as the shape of the truncated n-cross, i.e., the resulting lattice must be facet-transitive, and the mesotruncated {4,3,...,3,4} seems to be the only possible candidate.

Is my conjecture correct? Can it be proven? Suggestions of how to prove it would be greatly appreciated! :)
quickfur
Pentonian
 
Posts: 2935
Joined: Thu Sep 02, 2004 11:20 pm
Location: The Great White North

Re: n-cross tilings of n-space

Postby wendy » Thu Dec 19, 2013 7:15 am

The cells of the mesotruncate are centred on integer and integer-half coordinates.

The walls of the cells are set by max(x_1, 4*sum(abs(x_1)/n).

You first work out the fractional excess or defect of each coordinate, and if the absolute value adds to more than n-2, it rounds to a half-coordinate.

For example, consider 1.333, 2.666, 1.888. The first step is the ordinary cubic rounding: ie 1-0,333, 3-0.333 2-0.111. We see that the fractional parts add to 0.777, which is more than 0.75, so we need to consider the half-integer coordinate: 1.5-0.1666, 2.5+0.1666, 1.5+0.3888, The fractions add to 0.67777, which is less than 0.75, so the point is nearest the point 1.5, 2.5, 1.5
The dream you dream alone is only a dream
the dream we dream together is reality.

\ ( \(\LaTeX\ \) \ ) [no spaces] at https://greasyfork.org/en/users/188714-wendy-krieger
User avatar
wendy
Pentonian
 
Posts: 2014
Joined: Tue Jan 18, 2005 12:42 pm
Location: Brisbane, Australia

Re: n-cross tilings of n-space

Postby Klitzing » Thu Dec 19, 2013 9:35 am

It also is known as the Voronoi complex of the n-dimensional bcc lattice
(bcc = body centered hypercubic).
In case you are looking for further references.
--- rk
Klitzing
Pentonian
 
Posts: 1637
Joined: Sun Aug 19, 2012 11:16 am
Location: Heidenheim, Germany

Re: n-cross tilings of n-space

Postby quickfur » Thu Dec 19, 2013 4:36 pm

Thanks, Wendy!! I think that pretty much confirms my conjecture. Also, thanks, Klitzing, for pointing me to "body-centered cubic" -- that's the term I'm looking for. :)

One open question though: is the mesotruncated {4,3,...,3,4} better than the n-dimensional rhombic dodecahedral tiling that Wendy suggested earlier? The latter is also facet-transitive, and also easy to test for cell membership (in fact, in the 4D case, we have the interesting case that the mesotruncate o4o3x3o4o coincides with the 24-cell tiling of 4-space, which also coincides with the 4D rhombic dodecahedral tiling). If I'm not mistaken, these two tilings are dual to each other, is that correct?

Anyway, by "better" I mean the following. Basically, the n-cross is the ideal shape for my needs; so the closer the cell shape is to the n-cross, the better. Points outside of an embedded n-cross in the cell are unlikely to be useful. Suppose the cell has volume V1, and an embedded n-cross in the cell has volume V2. Then (V1-V2) represents the volume of points that are least likely to be useful. Thus, the lower the value of (V1-V2), the better the cell shape. So the question is, which cells have a lower (V1-V2) value: the cells of the mesotruncated {4,3,...3,4}, or the cells of the n-dimensional rhombic dodecahedral tiling?
quickfur
Pentonian
 
Posts: 2935
Joined: Thu Sep 02, 2004 11:20 pm
Location: The Great White North

Re: n-cross tilings of n-space

Postby quickfur » Fri Dec 20, 2013 2:20 am

Hmm. I've made a surprising discovery: the n-dimensional rhombic dodecahedron tiling of n-space is much better than the mesotruncated n-cube tiling in terms of closeness to the volume of an n-cross!

The volume of an n-dimensional rhombic dodecahedron is easy to calculate, since we can assemble it from two n-cubes by cutting the second n-cube into 2n (n-1)-cube pyramids, and attaching them to the facets of the first n-cube. If we inscribe this rhombic dodecahedron inside an n-cube of edge length E, then its volume would be twice the volume of an n-cube with edge length E/2, that is, V_rhomb = 2*(E/2)^n = E^n / (2^(n-1)).

The volume of a cell in the mesotruncated {4,3,...,3,4} at first glance appears rather complicated to calculate, but it's actually very easy once you realize that since the tiling is facet-transitive: take an n-cube, and cut out its middle section in the shape of a cell of this tiling. Since the tiling is facet-transitive, the remaining 2^n corners of the n-cube must be fragments of the 2^n cells centered on the n-cube's vertices, and these fragments can be reassembled into a second complete cell. Therefore, we have 2*V_meso = volume of n-cube = E^n, which gives V_meso = E^n / 2.

Now, our ideal cell shape is an n-cross, which has volume V_cross = E^n / n!, and it's easy to see that both types of cells fully enclose an n-cross, so the amounts of "wasted" space (i.e., volume outside an n-cross region) for each type of cell are:

W_meso = V_meso - V_cross = ... = E^n * (1/2 - 1/n!)
W_rhomb = V_rhomb - V_cross = ... = E^n * (1/(2^(n-1)) - 1/n!)

It's easy to see that for large n, the rhombic dodecahedral cells "waste" far less volume than the mesotruncated {4,3,...,3,4}'s cells. As n grows, W_meso approaches E^n / 2: the amount of wasted space approaches the entire volume of the cell! :o_o: In contrast, W_rhomb remains a small fraction of E^n.

So, in conclusion, the n-dimensional rhombic dodecahedral tiling is much closer to the ideal cell shape than the mesotruncated {4,3,...,3,4}. :| Fortunately, it retains most of the nice features I'm looking for: easy determination of cell membership and cell-transitive.

Interesting.
quickfur
Pentonian
 
Posts: 2935
Joined: Thu Sep 02, 2004 11:20 pm
Location: The Great White North

Re: n-cross tilings of n-space

Postby wendy » Fri Dec 20, 2013 8:05 am

We should look at the various lattices. We assume first a cubic lattice of 1, on which we hang all others.

In tegum units, the volume of a cross-polytope of diagonal D is D^n. The volume of a unit-edge cube is N!.

BCC rule: The equation for finding the nearest Body-centred cell, is to add the absolute fractions, plus or minus, relative to integers. If these are greater than N/2, then the point is referenced to the centre of the cube, otherwise, to the nearest vertex.

SC rule: The semicubic cell, for the integers adding to an even sum, the centre of that cell, for an odd one, one moves to the cell in the direction of the largest divergence from 0.5, and in that direction. So for 0,8888, 0.6666 and 0.4, we see the divergences are 0.3888, 0.1666, and 0.1, the first is largest, and we need to move in the positive region, ie we add (1,0,0) to the coordinate.

QC rule: The quarter-cubic works from 4D upwards, and uses both the BCC and SC.

A rule. The coordinate system for the simplex-based tiling is to use N+1 coordinates, the sum to be zero. Then, use the SC rule.

The ordinary cubic rule, where the cross polytopes sites with its vertices in the centre, makes use of a volume of 1 in N!

The SC rule by itself, where the cross polytope now has an edge of 2, sits in a volume of 2.N!, so we have 2^n in 2.N!

Joining the rules together, which works quite well in 4D and more, gives 2^n in N!.

The 4D case gives eg 16/24. It corresponds to putting a half-cube inside a cube, (since the cell of the quarter-cubic is a tesseract), but they all point the same way, which is different to what happens in {3,3,4,3}, where they alternate.

In 8D, you are putting 256 into 40320, which is about 1/160.

If one is prepared to use a matrix transform, one could squeeze a cross-polytope of edge sqrt(8) into a cell, which means that you are using 1/10 of the space. The determination of the cell would be the simple cubic rule, but you would then after extracting it, just transform the coordinate to get the desired point.

The maximun density of cross-polytopes in 8D, using 5_21 is 34560 in 40320, or 6/7. It's a bit better than spheres, where one can go no higher than 1/4.
The dream you dream alone is only a dream
the dream we dream together is reality.

\ ( \(\LaTeX\ \) \ ) [no spaces] at https://greasyfork.org/en/users/188714-wendy-krieger
User avatar
wendy
Pentonian
 
Posts: 2014
Joined: Tue Jan 18, 2005 12:42 pm
Location: Brisbane, Australia

Re: n-cross tilings of n-space

Postby quickfur » Sat Dec 21, 2013 3:37 am

wendy wrote:[...]
QC rule: The quarter-cubic works from 4D upwards, and uses both the BCC and SC.

What's the quarter-cubic rule?

A rule. The coordinate system for the simplex-based tiling is to use N+1 coordinates, the sum to be zero. Then, use the SC rule.

Doesn't this distort the distribution of points in the tiling though?

The ordinary cubic rule, where the cross polytopes sites with its vertices in the centre, makes use of a volume of 1 in N!

The SC rule by itself, where the cross polytope now has an edge of 2, sits in a volume of 2.N!, so we have 2^n in 2.N!

Joining the rules together, which works quite well in 4D and more, gives 2^n in N!.

The 4D case gives eg 16/24. It corresponds to putting a half-cube inside a cube, (since the cell of the quarter-cubic is a tesseract), but they all point the same way, which is different to what happens in {3,3,4,3}, where they alternate.

In 8D, you are putting 256 into 40320, which is about 1/160.

Right, this jives with what I've calculated.

If one is prepared to use a matrix transform, one could squeeze a cross-polytope of edge sqrt(8) into a cell, which means that you are using 1/10 of the space. The determination of the cell would be the simple cubic rule, but you would then after extracting it, just transform the coordinate to get the desired point.

Interesting. But what entries would be needed in the matrix? If it has irrational coefficients, then it's probably out of the question. :)

The maximun density of cross-polytopes in 8D, using 5_21 is 34560 in 40320, or 6/7. It's a bit better than spheres, where one can go no higher than 1/4.

This is interesting enough, but for my particular application, 8D is considered trivially low. More typical dimensions that I will be working with are around 20D for simple cases, and up to 100D for the complex cases. (If I had my way, I'd like to deal with even higher dimensions as well, but around 100D other factors begin to make it infeasible, such as the impractical amounts of time / space that would be needed to run the algorithm.)
quickfur
Pentonian
 
Posts: 2935
Joined: Thu Sep 02, 2004 11:20 pm
Location: The Great White North

Re: n-cross tilings of n-space

Postby wendy » Sat Dec 21, 2013 7:23 am

The quarter-cubic works by first using the BC rule to decide if to use the body-centred lattice, and then use the SC rule to determine if the cell is even or odd, and when it is odd, to move it to the appropriate even cell.

quickfur wrote: A rule. The coordinate system for the simplex-based tiling is to use N+1 coordinates, the sum to be zero. Then, use the SC rule.


Doesn't this distort the distribution of points in the tiling though?

The ordinary cubic rule, where the cross polytopes sites with i


The A-tiling is actually the same as the cross-polytope face, so there is no distortion here. The axies are more oblique than usual, though.

quickfur wrote:Interesting. But what entries would be needed in the matrix? If it has irrational coefficients, then it's probably out of the question


For dimensions of the form 2^n, the transform is in pure integers, but for the scope you want, the extraction is in the order of hundreds of calculations (20*20 = 400 dec). So you might be better sticking with quarter-cubic, or something like that, which is largely free of such things.

quickfur wrote:This is interesting enough, but for my particular application, 8D is considered trivially low. More typical dimensions that I will be working with are around 20D for simple cases, and up to 100D for the complex cases. (If I had my way, I'd like to deal with even higher dimensions as well, but around 100D other factors begin to make it infeasible, such as the impractical amounts of time / space that would be needed to run the algorithm.)


The reason it is better to stick with unrotated or simply rotated figures is that in 100 dimensions, you can have a lot of coordinates. On the other hand, if you stick with 100 dimensions, and use a something like 4D rotations (which makes a tegum of 2), you end up by dividing the hundred into eg 30, and have 30 * 16 calculations (ie hundred = six-score), calculations to get a double-size tegum in a unit-size cube. It's not much, but it's as efficient packing as using quarter-cubics, without the hassles.
The dream you dream alone is only a dream
the dream we dream together is reality.

\ ( \(\LaTeX\ \) \ ) [no spaces] at https://greasyfork.org/en/users/188714-wendy-krieger
User avatar
wendy
Pentonian
 
Posts: 2014
Joined: Tue Jan 18, 2005 12:42 pm
Location: Brisbane, Australia

Re: n-cross tilings of n-space

Postby quickfur » Tue Dec 24, 2013 3:31 am

wendy wrote:The quarter-cubic works by first using the BC rule to decide if to use the body-centred lattice, and then use the SC rule to determine if the cell is even or odd, and when it is odd, to move it to the appropriate even cell.

Hmm. I still don't see what difference this makes vs. using the BC rule or the SC rule directly?

quickfur wrote: A rule. The coordinate system for the simplex-based tiling is to use N+1 coordinates, the sum to be zero. Then, use the SC rule.


Doesn't this distort the distribution of points in the tiling though?

The ordinary cubic rule, where the cross polytopes sites with i


The A-tiling is actually the same as the cross-polytope face, so there is no distortion here. The axies are more oblique than usual, though.

Huh, interesting. Apparently this transformation doesn't introduce any distortions whatsoever! It just scales the coordinates by sqrt(2). Fascinating! So I was wrong about the A-tiling requiring a transformation involving irrationals (well, it does if distances are to be preserved, but there's no need to do that since we can just scale the cell sizes accordingly for the classification procedure. Thus, we retain integral coordinates, and the sqrt(2) factor is implicit and never needs to be represented explicitly). Maybe the omnitruncated A-tiling is feasible after all!

Now, how does one determine cell membership in the omnitruncated A-tiling, given the (n+1)-dimensional coordinates?

quickfur wrote:Interesting. But what entries would be needed in the matrix? If it has irrational coefficients, then it's probably out of the question


For dimensions of the form 2^n, the transform is in pure integers, but for the scope you want, the extraction is in the order of hundreds of calculations (20*20 = 400 dec). So you might be better sticking with quarter-cubic, or something like that, which is largely free of such things.

Right, that's what I thought.

quickfur wrote:This is interesting enough, but for my particular application, 8D is considered trivially low. More typical dimensions that I will be working with are around 20D for simple cases, and up to 100D for the complex cases. (If I had my way, I'd like to deal with even higher dimensions as well, but around 100D other factors begin to make it infeasible, such as the impractical amounts of time / space that would be needed to run the algorithm.)


The reason it is better to stick with unrotated or simply rotated figures is that in 100 dimensions, you can have a lot of coordinates. On the other hand, if you stick with 100 dimensions, and use a something like 4D rotations (which makes a tegum of 2), you end up by dividing the hundred into eg 30, and have 30 * 16 calculations (ie hundred = six-score), calculations to get a double-size tegum in a unit-size cube. It's not much, but it's as efficient packing as using quarter-cubics, without the hassles.

You have a good point; in high dimensions, there are a lot of coordinates to perform calculations for. I'm wondering if it might be worthwhile to consider a prism-based tiling, in which some of those coordinates can be disregarded for the purposes of classification into cells.
quickfur
Pentonian
 
Posts: 2935
Joined: Thu Sep 02, 2004 11:20 pm
Location: The Great White North

Re: n-cross tilings of n-space

Postby wendy » Tue Dec 24, 2013 7:46 am

Basically the Quarter-cubic is a 'body-centred' lattice, where each of the two cubics are then alternated into 'semicubic'. That's why we apply both rules. However the SC rule is considerably cheaper to implement, because the BC only doubles the packing for as many calculations, while the SC provides 2^(N-1) density.

The centres of the omnitruncate tiling are at every point a_x/(n+1), where the n+1 | (a_x1 - a_x0 ). For example, in seven dimensions, one has the point 1/8 1/8 9/8, 1/8. -7/8, -7/8, 1/8 1/8, all are incrimented by 1/8 over integer. Not sure on how to move a random point nearest this.

If you use stott-vectors, the thing could be quite painful in 100 dimensions, because the 100 vectors give 10000 multiples per vector. But if you convert the vectors into right vectors, and add them, you cut this down to 4600 multiples. You can greatly reduce this by using the add-and-multiply method to 100 or so. Still, it's an indication that using a right-angled coordinate system, and using right-angled coordinates.

If ye were going to plug say, 100 dimensions, and are looking for tegum-cells, i suspect it is best to use SC (since you can make the tegums 41% bigger), and not bother to rotate the cells any. A rotation to maximise the size is going to involve a 100*100 matrix, which is 10,000 calculations.

You do much better packing in the cells by using a composite body-centering rule, where the 'primary centre', is based on (sum of fractions), rounded to the nearest multiple of 4 on the primary diagonal. For a tiling of 113 D, you have 113 div 4 = 28, so this particular calculation is a simple addition, allows a packing of 28 semicubics into the same space the QC gives 2. By dividing 113 by some number, like 4, and treating each set separately, you get eg 2401 such packings (ie 7*7*7*7). Using sets of 3 are optimal: you get 59049 here, as you get the complete multiple of 12 at 108.

This is not a case of finding the nearest point, but finding its reference. As long as the points connected to the reference point contains exactly one tegum, and no further, then you are not obliged to go through the tedious process of finding some further point.
The dream you dream alone is only a dream
the dream we dream together is reality.

\ ( \(\LaTeX\ \) \ ) [no spaces] at https://greasyfork.org/en/users/188714-wendy-krieger
User avatar
wendy
Pentonian
 
Posts: 2014
Joined: Tue Jan 18, 2005 12:42 pm
Location: Brisbane, Australia


Return to Other Polytopes

Who is online

Users browsing this forum: No registered users and 16 guests

cron