H-representation to V-representation

Questions and problems about using polymake go here.
gordonfroyle
Posts: 15
Joined: 15 Feb 2011, 08:07

H-representation to V-representation

Postby gordonfroyle » 15 Feb 2011, 08:11

I want to take a half-space representation of a polyhedron and find the extreme points (and rays) - in other words do an H-rep to V-rep.

Apparently Fukuda's "cdd" program can do this, but I simply cannot compile his source code (either on Mac OS or Ubuntu).

I CAN however install polymake (Mac OS) without difficulty and obviously it contains "cdd" somewhere inside it... but I can't figure out how to specify a polyhedron in half-space form...

Any help gratefully received.

Gordon

herr
Developer
Posts: 40
Joined: 30 Dec 2010, 13:15

Re: H-representation to V-representation

Postby herr » 16 Feb 2011, 12:16

Thanks for asking this essential question!
You can define a polytope in polymake by specifing a matrix of POINTS or INEQUALITIES as follows:

Code: Select all

$inequalities=new Matrix<Rational>([[1,1,0],[1,0,1],[1,-1,0],[1,0,-1],[17,1,1]]); $p=new Polytope<Rational>(INEQUALITIES=>$inequalities);
Then you can ask for different properties (e.g. VERTICES in your case) of this polytope via

Code: Select all

print $p->VERTICES;
A list of properties that can be computed by polymake is available at http://polymake.org/release_docs/2.9.9/.
I just added a short description in our tutorial on polytopes on your question, which was obviously missing. Please have a look at it for details.

paffenholz
Developer
Posts: 211
Joined: 24 Dec 2010, 13:47

Re: H-representation to V-representation

Postby paffenholz » 16 Feb 2011, 13:50

polymake links with cddlib and lrslib for convex hull computations, there is no standalone version of cdd included that would work without polymake. polymake also contains its own implementation of beneath-beyond, and an interface to ppl.

As shown in the example in the previous post, in polymake you don't have to specify the particuar convex hull algorithm. polymake chooses one based on your input data and your request (and issue a notice when some external program is used for the first time).

If for some reason you want polymake to choose a particular one, say cdd, then you can tell polymake via a prefer statment, e.g.

Code: Select all

prefer 'cdd';
prior to your computations. This remains valid until you prefer some other convex hull code.

gordonfroyle
Posts: 15
Joined: 15 Feb 2011, 08:07

Re: H-representation to V-representation

Postby gordonfroyle » 16 Feb 2011, 23:44

My situation is that I am working with an unbounded polyhedron... at one "end" there are the vertices in which I am interested, but it is otherwise unlimited...

Perhaps I can bound it artificially by adding some other constraints, but if I don't, can polymake deal with it by keeping track of the "rays"?

paffenholz
Developer
Posts: 211
Joined: 24 Dec 2010, 13:47

Re: H-representation to V-representation

Postby paffenholz » 17 Feb 2011, 08:47

This is not a problem. polymake works with the homogenization of a polyhedron. The computed VERTICES have an additional first coordinate, which is either 0 or 1. Those rows with a leading 1 are the "true vertices" of the polyhedron, those that start with a 0 are the rays of the characteristic cone (see this page for background).

There are also some properties that deal specifically with the bounded part of a polyhedron. E.g. BOUNDED_VERTICES returns the row indices of the vertices of the polyhedron in VERTICES, i.e. the rows starting with a 1 (you can obtain a complete list of those properties dealing with boundedness by typing e.g. "apropos "BOUNDED";" in the shell (the properties are the capitalized words at the end of each line).

The current version of polymake does not officially support polyhedra with non-trivial lineality (i.e. containing an affine space), but convex hull computations should work.


Return to “Helpdesk”