Ordering of kD facets of nD polytope...?

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

Ordering of kD facets of nD polytope...?

Postby Paul » Sun Sep 19, 2004 3:45 pm

Hello all,

This is my first post on this message board. I'm an amateur mathematician.

Relating to face lattices of polytopes, with which Jonathan (PolyHedron Dude) has been helping me, I'm wondering about what various ways exist to order the kD facets of an nD polytope?

Do people usually just order the facets of the same dimension in some form of lexicographic order? If so, do any of these have any 'natural' geometric interpretation that works in any dimension? What are the various advantages and disadvantages associated with different conventions of ordering the facets?

With the face lattices, it appears that depending on how you order the vertices, you can get a different graph. It may be essentially the same in terms of connections between nodes, but it looks different anyway.

It'd be nice to be able to set some convention on the ordering of the kD facets so that comparsions between various face lattices might be made without having to wonder whether the face lattices being compared have utilized some different facet ordering convention.

It might also be nice to know how many, perhaps essentially similar in terms of connections between nodes, representations, and perhaps how to find those representations, exist for the face lattice of a given polytope.

Thanks
Paul
Trionian
 
Posts: 74
Joined: Sat Sep 04, 2004 10:56 pm

nD-hyperspheres...?

Postby Paul » Wed Sep 22, 2004 12:06 pm

Hello all,

I have a vague idea of a geometric possibility for the ordering of the kD facets of a nD (regular) polytope (n > k >= 0). For now, at least, I wish to restrict our polytope to being regular.

Perhaps... again, I'm not sure this will go anywhere helpful...

Put the centroid(? not sure this has a well-established definition, but I suspect you know what I mean...) of the (regular) polytope at the origin and inscribe the polytope in an nD-hypersphere.

Then, using a Euclidean coordinate system (x,y,z,w,... p,q), as usual marking off distances on orthogonal 1D lines from the origin, choose the last coordinate, here q, and traverse the hypersurface from the maximum q of the nD-hypersphere inscribing the polytope to the maximum -q also inscribing the polytope.

Of course, the course I suggest will find us setting out a (n-1)D hypersurface on the nD-hypersphere as we traverse from q to -q.

Continue proceeding to set out the (n-1)D hypersurface traversing the nD-hypersphere until a kD facet of the polytope is intersected by the (n-1)D hypersurface.

At this point, form an (n-2)D hypersurface orthogonal(? I'm not entirely sure...) to the (n-1)D hypersurface at the point of intersection between the (n-1)D hypersurface and the kD facet of the polytope... and traverse this similar to how we are traversing the nD-hypersphere.

Continue forming and traversing (n-t)D hypersurfaces until one gets to a 2D-hypersurface, which I believe will be a circle.

Traverse the circle from the last point of next highest hypersurface intersection, in a counterclockwise direction, using the maximal coordinate (the rightmost) aribitrarily choosen ordering of coordinates in our Euclidean coordinate system (x,y,z,w,... p,q), to define a perspective to assign clockwise directions.

The first kD facet encounted will be numbered the first, or r+1, and then, the next one, the second, or r+2.

After the circle has been completely traversed, increase dimensionality by traversing the series of intersecting hypersurfaces reverse of the direction used for getting to the circle from the nD-hypersphere.

Once you've returned to the nD-hypersphere again at the original hypersurface point of intersection, continue down the nD-hypersphere, continuing to sweep out a (n-1)D hypersurface, until another point of intersection with a kD facet of the polytope is encountered,... and continue in the same fashion until the nD-hypersphere has been fully traversed.

Please... be kind. This is only a very rough idea of a concept which may not work at all. And probably still needs much greater description to be employed.

Hopefully someone here can clarify whether this method of geometric description... makes any sense. If not, might something similar make some sense...? Or, either way, perhaps someone can improve the description?

Thanks
Paul
Trionian
 
Posts: 74
Joined: Sat Sep 04, 2004 10:56 pm

Postby pat » Wed Sep 22, 2004 2:21 pm

Your description sounds fine except that you will get a different ordering depending upon whether there is a vertex at the top or an edge at the top.

Let this ordering be represented here by the sequence of dimensions of facets encountered. For example, finding a 2-d face, then a 1-d face, then a vertex, then a 2-d face would be: { 2, 1, 0, 2 }.

For example, take a triangle inscribed in a circle. Here, you would either hit a vertex first giving you an ordering of { 0, 1, 1, 0, 1, 0 } or you would hit an edge first, giving you an ordering of { 0, 1, 0, 1, 1, 0 }.

More in a separate post.
pat
Tetronian
 
Posts: 563
Joined: Tue Dec 02, 2003 5:30 pm
Location: Minneapolis, MN

Postby pat » Wed Sep 22, 2004 2:55 pm

I've given this topic a bunch of thought in the last few days. I haven't yet come up with anything really useful.

It seems to me that the problem is much simpler if the polytope is *not* regular.

I've been working mostly with the face lattice. The last thing I was playing with is giving each node in the face lattice both an upward and a downward "flow". The node in the face lattice for the empty facet has an upward flow of one. This is evenly distributed amongst the nodes which point to it. So, if there are eight vertexes, each of them would get 1/8-th upward flow. Each of those nodes would distribute their flow evenly amongst the nodes immediately above them in the lattice, etc. until you get to the node which represents that full polytope. At that point, you should have gotten all of the flow back. So, it has an upward flow of one.

Repeat this process for downward flow starting at the polytope node and working back toward the empty facet node.

Now, you have two numbers, u and d for each node. Both are on the range (0,1]. Order the kD-facets in the lattice according to the whatever sorting of these (u,d) you like. Since it's supposed to be "flow", I've kinda been thinking of each node as having a complex flow: u + di and then sorting them so that a ≥ b if |a| > |b| or |a| = |b|, a<sub>d</sub> ≥ b<sub>d</sub>.

This does abysmally though at ordering regular polytopes since each kD facet would have the same flow. But, for non-regular graphs, it can really help sorting out whether the two are isomorphic. It's, unfortunately, not conclusive. I'm pretty sure there are non-isomorphic graphs with identical flows. And, I'm pretty sure that there can be some nodes in the graph with identical flows that are really in very geometrically different areas (for this, I'm picturing a sort of bulbous polytope with pointy bits sticking out and imagining that there could be some ways to arrange the polytope so that the flow at an edge or vertex in a pointy bit sticking off of another pointy bit is the same as the flow at an edge or vertex in a pointy bit that sticks off of the main bulb. But, I don't have any particular working example in mind right now.)

Also, this flow approach doesn't distinguish between topologically equivalent but geometrically distinct polytopes as one might like. I dunno. Maybe a natural ordering would be to start with the largest (by area) facet first. And, maybe, for your purposes, you can impose an orientation on the faces of the polytope. Rambling...
pat
Tetronian
 
Posts: 563
Joined: Tue Dec 02, 2003 5:30 pm
Location: Minneapolis, MN

Postby Paul » Wed Sep 22, 2004 4:58 pm

Hello Pat,

Thanks for your response.

It kinda sounds like (I'm not certain...) you may be trying to put ALL the facets of a polytope, of whatever dimension, into one ordering.

Perhaps I didn't make it clear, but I'm not really trying to do that. I'm just trying to order the facets of a polytope for any 1 given dimension, k. Of course, one could apply the ordering to any dimension k of a set of facets, n > k >= 0.

So, the nD-hypersphere would be traversed from q to -q for every set of kD facets of the polytope. So, they'd not be any one traversal of this nature that would intersect a 1D edge and a 0D point... or, the intersection of facets of different dimensions would be ignored. The only intersections that would be responded to would be the ones with k dimension facets.
Paul
Trionian
 
Posts: 74
Joined: Sat Sep 04, 2004 10:56 pm

Postby pat » Wed Sep 22, 2004 5:51 pm

Ahh... okay... I'm still thinking that with some orientations of, say, a cube, you'll come across four faces that meet at a corner and then four faces that meet at the opposite corner. Whereas with a different starting orientation, you'd come across a single face. Then, the four faces that border it. Then, the remaining face. You can overcome this, I suppose, by starting the polytope in what's called "general position" where no facet normals are parallel to any world axis. (I may be cutting the definition of "general position" too short... but I think you get the idea... put the polytope so that none of the facets line up with the coordinate system).

I thought one of your unstated goals was to make the ordering unique (up to symmetry), or to be able to sort the face-lattice in some way so that it's easier to tell if two face lattices are isomorphic.
pat
Tetronian
 
Posts: 563
Joined: Tue Dec 02, 2003 5:30 pm
Location: Minneapolis, MN

Postby Paul » Wed Sep 22, 2004 7:50 pm

Hello Pat,

Thanks for your response.

"I thought one of your unstated goals was to make the ordering unique (up to symmetry), or to be able to sort the face-lattice in some way so that it's easier to tell if two face lattices are isomorphic."

Yes. I think(!) those are kinda some of my goals. However, certainly the latter goal of being able to "sort the face-lattice in some way so that it's easier to tell if two face lattices are isomorphic" is kinda an extended mission goal, if you will.
Paul
Trionian
 
Posts: 74
Joined: Sat Sep 04, 2004 10:56 pm

Postby Paul » Sat Sep 25, 2004 8:22 pm

I posted some nature of continuation of this thread on the Math Message Board... http://www.math2.org/mmb/, where I know how to use graphics... Face lattices, ordering of kD facets of polytopes... http://www.math2.org/cgi-bin/mmb/server?action=read&msg=30810

Perhaps some of you can respond on the Math Message Board. Or here. Either way.
Paul
Trionian
 
Posts: 74
Joined: Sat Sep 04, 2004 10:56 pm


Return to Other Polytopes

Who is online

Users browsing this forum: Google [Bot] and 8 guests

cron