Algorithm for polytope slicing

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

Algorithm for polytope slicing

Postby quickfur » Mon Nov 27, 2006 12:38 am

Recently, I've been trying to design an algorithm to solve the following problem:

Given:
(1) a polytope P with vertices V and its full face lattice L (where members of L are represented as subsets of V, and the partial order is imposed by the subset relation)
(2) a half-space H = {x|N*x + C < 0}
Find:
The intersection P' of P and H. The full face lattice of P' is required, of course, along with its vertices V'.

I believe I have a workable algorithm, although I have yet to verify all of its details. In the meantime, I'd be interested to hear from everyone else. :)
quickfur
Pentonian
 
Posts: 2935
Joined: Thu Sep 02, 2004 11:20 pm
Location: The Great White North

Postby bo198214 » Mon Nov 27, 2006 1:34 pm

Hey, thats my question!

You can do it recursively.
The (non-degenerated) cut of an n-dim polytope is a polytope of dimension n-1.
So for a polytope of dimension n, look simply at it facets (of dimension n-1) and cut the facets by recursion assumption, thereby getting a set of cuts of dimension n-2 which together (as facets) are a facet (of dimension n-1).
This facet and the corresponding right sides of the cutted facets are the intersection with the halfspace or right side of a cutting plane with the original polytope.

This algorithm is recursive (i.e. cuts facets of dimension n-1). So we have to supply an induction start. This is to cut a a line from a to b. But it is clear how to do it. Or we can even start with a point.

Of course one have to be a bit careful with the degenerated cases i.e. if the halfplane intersects at only a point or at a line or at a face. But this is left to the programmer ;). Also simple case that the cut is empty was omitted (then the original face lies completely on the left or right side of the cutting plane.)
bo198214
Tetronian
 
Posts: 692
Joined: Tue Dec 06, 2005 11:03 pm
Location: Berlin - Germany

Postby quickfur » Mon Nov 27, 2006 4:39 pm

bo198214 wrote:Hey, thats my question!

You can do it recursively.
The (non-degenerated) cut of an n-dim polytope is a polytope of dimension n-1.
So for a polytope of dimension n, look simply at it facets (of dimension n-1) and cut the facets by recursion assumption, thereby getting a set of cuts of dimension n-2 which together (as facets) are a facet (of dimension n-1).
This facet and the corresponding right sides of the cutted facets are the intersection with the halfspace or right side of a cutting plane with the original polytope.

This algorithm is recursive (i.e. cuts facets of dimension n-1). So we have to supply an induction start. This is to cut a a line from a to b. But it is clear how to do it. Or we can even start with a point.

Very good. So how do you assemble the face lattice of the resulting polytope?

Of course one have to be a bit careful with the degenerated cases i.e. if the halfplane intersects at only a point or at a line or at a face. But this is left to the programmer ;). Also simple case that the cut is empty was omitted (then the original face lies completely on the left or right side of the cutting plane.)

You also need to take care of the case where the cut of the polytope is non-degenerate, but the cut of a face is degenerate: e.g., if the hyperplane intersects an n-dimensional face at one of its (n-k)-subfaces, such as intersecting one of the faces, edges, or vertices of a cubical facet (instead of cutting through the middle of the facet).
quickfur
Pentonian
 
Posts: 2935
Joined: Thu Sep 02, 2004 11:20 pm
Location: The Great White North

Postby bo198214 » Mon Nov 27, 2006 9:10 pm

quickfur wrote:So how do you assemble the face lattice of the resulting polytope?

Oh, I shirk assembling the face lattice by regarding a polytope just given by its facets. (From which you can then recursively compute the face lattice.)
You also need to take care of the case where the cut of the polytope is non-degenerate, but the cut of a face is degenerate: e.g., if the hyperplane intersects an n-dimensional face at one of its (n-k)-subfaces, such as intersecting one of the faces, edges, or vertices of a cubical facet (instead of cutting through the middle of the facet).


But the degenerate cases are essentially not different from the case that the plane does not intersect at all. Of course depending on what you want to do. For what I want to do, for example if I cut a polytope, I get 3 things, the left side, the cut, and the right side.
And if I cut at a facet for example, the left side would be empty and the right side the whole polytope, and not: the left side empty and the right side the polytope without one facet, and also not: the left side that facet, and the right side the whole polytope or so.
But of course that may vary regarding different applications of that algorithm.
bo198214
Tetronian
 
Posts: 692
Joined: Tue Dec 06, 2005 11:03 pm
Location: Berlin - Germany

Postby quickfur » Mon Nov 27, 2006 10:35 pm

bo198214 wrote:
quickfur wrote:So how do you assemble the face lattice of the resulting polytope?

Oh, I shirk assembling the face lattice by regarding a polytope just given by its facets. (From which you can then recursively compute the face lattice.)

Well, then this problem is no problem at all, since you could just add the halfspace equation to the facet equations and invoke vertex/face enumeration algorithm. :) The whole point was that if you were given the face lattice, you want to take advantage of that so that you don't recompute the entire face lattice of the result.

You also need to take care of the case where the cut of the polytope is non-degenerate, but the cut of a face is degenerate: e.g., if the hyperplane intersects an n-dimensional face at one of its (n-k)-subfaces, such as intersecting one of the faces, edges, or vertices of a cubical facet (instead of cutting through the middle of the facet).


But the degenerate cases are essentially not different from the case that the plane does not intersect at all. Of course depending on what you want to do. For what I want to do, for example if I cut a polytope, I get 3 things, the left side, the cut, and the right side.

But this happens not only at the polytope level, but also at the facet level. For example, if I cut a cube such that the cutting plane lies along exactly one of its edges, then two of the cubes faces will have the plane touching one of their edges, but it should not cut off that edge or introduce a new face (of height 0). Another two faces will have the plane touching one of their vertices and cutting another edge, so a new edge is introduced between the existing vertex and the intersecting point on the other edge. Finally, one face will have the plane cut parallel to two of its edges, so two new vertices are introduced and should be joined by a new edge. Also, the edge lying on the plane should be untouched.

Of course, all of this is easy at the abstract level, but if you're computing the new face lattice from the original, you have to handle these cases differently.

And if I cut at a facet for example, the left side would be empty and the right side the whole polytope, and not: the left side empty and the right side the polytope without one facet, and also not: the left side that facet, and the right side the whole polytope or so.
But of course that may vary regarding different applications of that algorithm.

Correct. So the logic behind it is very simple; the tricky part is in the details. Given the set of vertices V and the face lattice L (the elements of which are vertex sets representing which vertices lie on the face), every (d-1)-face is only stored once even though it may be shared by multiple d-faces. So when you compute the intersections, you have to correctly recompute the vertex sets of the d-faces without duplicating any new (d-1)-faces.
quickfur
Pentonian
 
Posts: 2935
Joined: Thu Sep 02, 2004 11:20 pm
Location: The Great White North

Postby bo198214 » Tue Nov 28, 2006 12:08 am

quickfur wrote:
bo198214 wrote:Oh, I shirk assembling the face lattice by regarding a polytope just given by its facets. (From which you can then recursively compute the face lattice.)

Well, then this problem is no problem at all, since you could just add the halfspace equation to the facet equations and invoke vertex/face enumeration algorithm. :) The whole point was that if you were given the face lattice, you want to take advantage of that so that you don't recompute the entire face lattice of the result.

Oh come on quickfur, that was surely not what I meant! Each (d dim) polyhedron is given by its (d-1 dim) facets. Each facet is a polyhedron, the 0-dimensional polyhedron is a point - a recursive definition.
The algorithm computes the two polyhedrons that are the result of cutting a polyhedron by a (hyper)plane, like a potatoe by a knife.
I simply didnt know what else do you wanted to have.

But this happens not only at the polytope level, but also at the facet level.

Yes, but the facets are polyhedrons itself. So there is nothing special about it.
The best strategy is to handle degenerated cuts (i.e. where the face lies completely in the hyperplane) like no cuts. I dont see where this would fail, also not in the cube example you gave.
If I cut off the infinitesimal small skin of the potatoe it looks after the cut the same.

Given the set of vertices V and the face lattice L (the elements of which are vertex sets representing which vertices lie on the face), every (d-1)-face is only stored once even though it may be shared by multiple d-faces. So when you compute the intersections, you have to correctly recompute the vertex sets of the d-faces without duplicating any new (d-1)-faces.

As I already told for the recursive algorithm it is (also mentally and programaticly) easier to rely on a recursive structure, not a face lattice. Though the recursive structure is not far away from the face lattice.
bo198214
Tetronian
 
Posts: 692
Joined: Tue Dec 06, 2005 11:03 pm
Location: Berlin - Germany

Postby quickfur » Tue Nov 28, 2006 4:57 pm

bo198214 wrote:
quickfur wrote:
bo198214 wrote:Oh, I shirk assembling the face lattice by regarding a polytope just given by its facets. (From which you can then recursively compute the face lattice.)

Well, then this problem is no problem at all, since you could just add the halfspace equation to the facet equations and invoke vertex/face enumeration algorithm. :) The whole point was that if you were given the face lattice, you want to take advantage of that so that you don't recompute the entire face lattice of the result.

Oh come on quickfur, that was surely not what I meant! Each (d dim) polyhedron is given by its (d-1 dim) facets. Each facet is a polyhedron, the 0-dimensional polyhedron is a point - a recursive definition.
The algorithm computes the two polyhedrons that are the result of cutting a polyhedron by a (hyper)plane, like a potatoe by a knife.
I simply didnt know what else do you wanted to have.

I was referring to computing the face lattice recursively, not the algorithm. Sorry.

But this happens not only at the polytope level, but also at the facet level.

Yes, but the facets are polyhedrons itself. So there is nothing special about it.
The best strategy is to handle degenerated cuts (i.e. where the face lies completely in the hyperplane) like no cuts. I dont see where this would fail, also not in the cube example you gave.
If I cut off the infinitesimal small skin of the potatoe it looks after the cut the same.

Ah, OK, I see what you're saying now. :oops:

Given the set of vertices V and the face lattice L (the elements of which are vertex sets representing which vertices lie on the face), every (d-1)-face is only stored once even though it may be shared by multiple d-faces. So when you compute the intersections, you have to correctly recompute the vertex sets of the d-faces without duplicating any new (d-1)-faces.

As I already told for the recursive algorithm it is (also mentally and programaticly) easier to rely on a recursive structure, not a face lattice. Though the recursive structure is not far away from the face lattice.

Well, that was not the stated problem, though. The stated problem is that you are given a face lattice, and you need to compute the output in the same form. Of course your algorithm will work, that's not in question. The issue here is how to apply it to a face-lattice representation of the polytope.
quickfur
Pentonian
 
Posts: 2935
Joined: Thu Sep 02, 2004 11:20 pm
Location: The Great White North

Postby bo198214 » Tue Nov 28, 2006 7:09 pm

Well, that was not the stated problem, though. The stated problem is that you are given a face lattice, and you need to compute the output in the same form. Of course your algorithm will work, that's not in question. The issue here is how to apply it to a face-lattice representation of the polytope.


For my sake it suffices to convert face lattice -> face-subfacet structure then apply the algorithm and then convert face-subfacet structure -> face lattice.
I think the face-lattice (as set of sets) is simply not appropriate for the problem.
If you would ask me how to divide roman numerals, then I would tell you convert it to decimal (or binary) system, apply the straight division algorithm and then convert it back to the roman numerals.

The face lattice is however not that far from the face-subfacets structure. The edges in the Hasse-Diagram correspond to the face-subfacet relation. Computing the Hasse-Diagram maybe O(n<sup>2</sup>), n the number of faces and subset testing seen as constant. And from a given Hasse-Diagram (with the lowest elements identified by the vertices) it should be O(n) to compute the face-lattice (union seen as constant).
For every node of the Hasse-Diagram you simply need to compute the contained vertices, and this can be done recursively by taking the union of the vertex sets of the sub-facets.
bo198214
Tetronian
 
Posts: 692
Joined: Tue Dec 06, 2005 11:03 pm
Location: Berlin - Germany

Postby quickfur » Wed Nov 29, 2006 2:39 am

bo198214 wrote:
Well, that was not the stated problem, though. The stated problem is that you are given a face lattice, and you need to compute the output in the same form. Of course your algorithm will work, that's not in question. The issue here is how to apply it to a face-lattice representation of the polytope.


For my sake it suffices to convert face lattice -> face-subfacet structure then apply the algorithm and then convert face-subfacet structure -> face lattice.
I think the face-lattice (as set of sets) is simply not appropriate for the problem.
If you would ask me how to divide roman numerals, then I would tell you convert it to decimal (or binary) system, apply the straight division algorithm and then convert it back to the roman numerals.

Heh. If I were to do it, I'd prefer hexadecimal. ;)

The face lattice is however not that far from the face-subfacets structure. The edges in the Hasse-Diagram correspond to the face-subfacet relation. Computing the Hasse-Diagram maybe O(n<sup>2</sup>), n the number of faces and subset testing seen as constant. And from a given Hasse-Diagram (with the lowest elements identified by the vertices) it should be O(n) to compute the face-lattice (union seen as constant).
For every node of the Hasse-Diagram you simply need to compute the contained vertices, and this can be done recursively by taking the union of the vertex sets of the sub-facets.

Hmm. Now you make me wonder, what's the best structure for representing polytopes? I chose the lattice representation because it is O(1) to decide whether a subface is contained by another subface.
quickfur
Pentonian
 
Posts: 2935
Joined: Thu Sep 02, 2004 11:20 pm
Location: The Great White North

Postby bo198214 » Wed Nov 29, 2006 11:50 am

quickfur wrote:Hmm. Now you make me wonder, what's the best structure for representing polytopes? I chose the lattice representation because it is O(1) to decide whether a subface is contained by another subface.


But it is not completely clear for me how exactly you represent the face lattice. I would guess you have more than just a set of sets? At least the dimension attached to each face?

The Hasse-Diagram is the face-subfacet relation (i.e. between dimension m and m-1). If you really need the face-subface (i.e. over more dimensions) relation, you can of course attach the vertex set to each face. We have seen it is computable with nearly no effort from the Hasse-Diagram.

Or you can also make a tree-search from the upper face to the subface, which has the same effort O(n). I dont know how you represent sets but usually set comparison depends on the number of elements in the sets, in this case the vertices. So the tree search would be an even more performant way.
bo198214
Tetronian
 
Posts: 692
Joined: Tue Dec 06, 2005 11:03 pm
Location: Berlin - Germany

Postby quickfur » Thu Nov 30, 2006 11:11 pm

bo198214 wrote:
quickfur wrote:Hmm. Now you make me wonder, what's the best structure for representing polytopes? I chose the lattice representation because it is O(1) to decide whether a subface is contained by another subface.


But it is not completely clear for me how exactly you represent the face lattice. I would guess you have more than just a set of sets? At least the dimension attached to each face?

I have a numbered list of vertices, and a table of faces keyed by dimension. Each dimension contains a list of facets, which are sets of vertices. Set operations (union, intersection) are O(1).

The Hasse-Diagram is the face-subfacet relation (i.e. between dimension m and m-1). If you really need the face-subface (i.e. over more dimensions) relation, you can of course attach the vertex set to each face. We have seen it is computable with nearly no effort from the Hasse-Diagram.

Or you can also make a tree-search from the upper face to the subface, which has the same effort O(n). I dont know how you represent sets but usually set comparison depends on the number of elements in the sets, in this case the vertices. So the tree search would be an even more performant way.

Well, my current representation of vertex sets is quite efficient for small polytopes (less than 100 vertices), virtually O(1). But for very large polytopes, say thousands or millions of vertices, a tree search would be better. Also, the vertex set representation is harder to iterate over.
quickfur
Pentonian
 
Posts: 2935
Joined: Thu Sep 02, 2004 11:20 pm
Location: The Great White North


Return to Other Polytopes

Who is online

Users browsing this forum: No registered users and 15 guests