Finding vertices of a complex polytope

[Nobody]

Given at least N+1 N-dimensional half-spaces defined by implicit plane
equations, how would I find the vertices of the convex polytope comprising
the intersection of the half-spaces?

A brute-force approach is straightforward: any set of N non-parallel
planes define a point, which can then be tested against any remaining
planes. For exactly N+1 planes, there are N+1 ways to choose N planes,
giving the N+1 vertices of the polytope. But additional planes result in
a combinatorially-increasing number of choices, and also an increasing
amount of work required to test each resulting point against the remaining
planes.

So: can anyone recommend a better algorithm?

[Nicolas Bonneel]

Hi,
my boss was looking at the same problem a few months ago. He came up
with a few papers, one of which was doing a kind of "inverted" simplex
algorithm... I'll ask him for the references.

Cheers

[Nicolas Bonneel]

Here it is :
http://www.springerlink.com/content/m7440v7p3440757u/

[Nobody]

On Wed, 11 Jan 2012 17:26:30 +0100, Nicolas Bonneel wrote:

> Here it is :
> http://www.springerlink.com/content/m7440v7p3440757u/

Thanks.