Algorithm to compute properties of polytopes

[quickfur]

Does any know what's the best algorithm for deriving various properties of (non-regular) convex polytopes, such as the ridges, vertices, etc., given only the equations of the bounding hyperplanes?

I came up with the following algorithm, but it's very inefficient: O(n!). Does anyone know a better way of doing this?

In the following, a hyperplane in Rⁿ is defined by a normal vector N and a constant displacement factor C: it is the set { x in Rⁿ | N.x + C = 0 }. A half-space corresponding to H is defined to be: { x in Rⁿ | N.x + C <= 0 }.

A (non-regular) convex polytope P in Rⁿ is defined to be the intersection of the half-spaces corresponding to its bounding hyperplanes: P = intersection of H₁ ... H_m for some positive integer m.

Given H₁ ... H_m, we want to compute its vertices, edges, ridges, facets, etc.. Here's one way of doing this (unfortunately inefficient):

For each H_i:
1) find a linear transformation T_i that maps H_i to the horizontal hyperplane H₀. H₀ is simply the subspace of Rⁿ where all points have their last Cartesian coordinate equal to 0.

2) For each j != i, compute the intersection of T_i(H_j) with H₀. The result of this intersection is a ridge (an (n-2)-dimensional plane) in Rⁿ, but it is a hyperplane in R^n-1. The set of all these hyperplanes in R^n-1 defines a polytope Q that corresponds with the facet F_i of P which is coplanar with H_i. That is, T_i^-1(Q) = F_i.

3) Recursively apply this algorithm to this face polytope, until we reach R¹, in which case we have computed the vertices, edges, ridges, etc., for Q. Applying the inverse transformation T_i^-1 yields the coordinates of these vertices, edges, etc., in Rⁿ.


If I didn't miss anything obvious, this should compute all the vertices, edges, planes, etc., of the polytope P. The only problem is that it's extremely inefficient due to the deep recursion. Is there a better way of doing these computations?

[pat]

I haven't looked at your algorithm too closely. But, for my raytracer, I did a convex-hull algorithm. I'm sure there are better ones out there. But, I was really able to bring things down from O(n!) to O(n²) by starting out with k-points (in k-dimensions) and adding one point at a time from there.

[quickfur]

I haven't looked at your algorithm too closely. But, for my raytracer, I did a convex-hull algorithm. I'm sure there are better ones out there. But, I was really able to bring things down from O(n!) to O(n²) by starting out with k-points (in k-dimensions) and adding one point at a time from there.

The problem, though, is that I'm starting from hyperplane equations (I already know the normals and the displacements) and I want to derive the vertices, edges, etc.. The convex hull algorithms I've seen appear to go the other way: given a set of points, compute the hyperplane normals, etc.

[pat]

Yes, I agree... the process I described was backwards. But, the same sort of principle applies.

Start with one hyperplane. Assuming that you don't have redundancy in your set of hyperplanes, you now know the equation of one face of the polytope.

Add a second hyperplane. Now, you know the equation of a second face and one potential ridge of the polytope.

Add a third hyperplane. Now, you know the equation of a third face and two potential ridges of the polytope and one potential (d-3)-facet. If your old potential ridge was above this hyperplane, then it isn't really a ridge.

I believe this whole process is O(n²). Actually, I suppose it's O(n²) if you're just looking for all of the vertices or all of the ridges. It may be messier if you're looking for all of the inclusions.

But, I think you can keep it down to at least O(d * n²) for a d-dimensional set of n-hyperplanes if you find all of the ridges, then lather rinse and repeat with each ridge. Actually, that's not right though... since there may well be more than n ridges. But, I don't think it goes factorial on you anywhere.

[quickfur]

Yes, I agree... the process I described was backwards. But, the same sort of principle applies.

OK. Oh, and btw, I've found out the proper name for what I'm trying to do... it's called the Vertex Enumeration Problem, only I'm finding more than just the vertices, but the ridges, edges, etc., as well.

Start with one hyperplane. Assuming that you don't have redundancy in your set of hyperplanes, you now know the equation of one face of the polytope.

Add a second hyperplane. Now, you know the equation of a second face and one potential ridge of the polytope.

Add a third hyperplane. Now, you know the equation of a third face and two potential ridges of the polytope and one potential (d-3)-facet. If your old potential ridge was above this hyperplane, then it isn't really a ridge.

Cool! This is a very good idea. Much better than my naive approach of recursively looping over each hyperplane. Although, I'm not sure how to represent all these intermediate results efficiently. E.g., what's the best way to represent a ridge, so that it's easy to perform further operations (intersections with other ridges, etc.) on it? I'm thinking in terms of the types of data structures that I will need.

I believe this whole process is O(n²). Actually, I suppose it's O(n²) if you're just looking for all of the vertices or all of the ridges. It may be messier if you're looking for all of the inclusions.

It's probably a little more than n², since I want to enumerate all faces (including facets (d-1), ridges (d-2), edges, vertices).

But, I think you can keep it down to at least O(d * n²) for a d-dimensional set of n-hyperplanes if you find all of the ridges, then lather rinse and repeat with each ridge. Actually, that's not right though... since there may well be more than n ridges. But, I don't think it goes factorial on you anywhere.

OK, I don't think it was a factorial after all, I think I miscalculated. My algorithm iterates over n hyperplanes, and for each hyperplane it computes the intersection with the (n-1) other hyperplanes to yield the ridges. This procedure is then recursively applied to the facet on the hyperplane (i.e., it computes the intersections of all the ridges), etc.. So the recursion depth is d, and at each level the complexity is O(n²). So you're right, it's O(d*n²), not O(n!).

The problem with my approach, though, is that it does many redundant computations (the intersection of each pair of hyperplanes is computed twice; each vertex is arrived at m times, where m is the order of the vertex).

I considered a combinatorial approach, to take advantage of the fact that every ridge corresponds with the intersection of a pair of hyperplanes, every (d-i) face corresponds with the intersection of i hyperplanes. Essentially, computing the intersections of all subsets of d or less members of the set of hyperplanes. The problem is how to decide whether a given intersection lies outside the polytope proper. Maybe your approach is still better.