Is X an edge of the polytope Y?

General discussion on polymake goes here.
Isaac
Posts: 5
Joined: 29 Sep 2014, 21:03

Is X an edge of the polytope Y?

Postby Isaac » 29 Sep 2014, 21:17

Hello,


Hopefully there's someone out there who can help me with this. I want to be able to answer the following question:

"F is a set of vectors in the semigroup N^d (d copies of the the non-negative integers). Define P = conv(F) i.e. the convex hull of F. Given u_1 and u_2 in F, is [u_1, u_2] an edge of P?"

I have thousands of sets F that I must analyse in this fashion e.g see attached file for a sample F. Is there a fast way to answer this question in general? I have used the commands print $p->VERTICES, print $p->GRAPH->EDGES etc in polymake but this method is too slow and cumbersome.


Thanks in advance,


Isaac

User avatar
joswig
Main Author
Posts: 279
Joined: 24 Dec 2010, 11:10

Re: Is X an edge of the polytope Y?

Postby joswig » 30 Sep 2014, 15:07

This can be answered by solving a linear program. In fact, this function is implemented in polymake, but not quite in the form that you want. However, from our source code this is only a minor variation.

There is the client graph_from_vertices whose source code resides in apps/polytope/src and which sets up these LPs for any pair of vertices of a bounded polyhedron. This is also called by default provided that you are asking for GRAPH.ADJACENCY and you only have the VERTICES.

Checking if an input point is actually a vertex can be solved by a similar LP. See also the function separating_hyperplane.

See also this thread.

Isaac
Posts: 5
Joined: 29 Sep 2014, 21:03

Re: Is X an edge of the polytope Y?

Postby Isaac » 30 Sep 2014, 17:40

Hi Joswig,


Thanks for your comment. Unfortunately I'm not a great programmer, hence would it be possible for you to elaborate a little on your advice? My input files contain row vectors like the following

0 2 0 0 0 0 0 0 0 0 0 0 0 0 1 1

0 1 0 0 0 1 0 0 0 0 1 0 0 0 0 1

0 1 0 0 0 1 0 0 0 0 0 1 0 0 1 0

0 0 0 0 0 0 0 2 1 1 0 0 0 0 0 0

0 0 0 0 0 1 0 1 0 1 1 0 0 0 0 0

0 0 0 0 0 0 1 1 0 2 0 0 0 0 0 0

0 0 0 0 0 1 0 1 1 0 0 1 0 0 0 0

which may or may not contain interior points of the convex hull i.e. there may be non-vertices in the file. Ideally I would like a program to return the set of pairs (u_1,u_2) where [u_1,u_2] is an edge of P. What steps would I have to take to write such a program?

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

Re: Is X an edge of the polytope Y?

Postby paffenholz » 30 Sep 2014, 21:38

polymake should already be the correct answer to this. Do you want a list of pairs of vertices or a list of pairs of indices?

The first can e.g. be solved by

Code: Select all

$c=new Polytope(POINTS=>[[1,0,0],[1,2,0],[1,2,1],[1,2,2],[1,0,2]]); $a=new Set<Set<Vector>>; foreach $e (@{$c->GRAPH->EDGES}) { $a+=new Set<Vector>(map ($c->VERTICES->[$_],@{$e})); } print $a; {{<1 0 0> <1 0 2>} {<1 0 0> <1 2 0>} {<1 0 2> <1 2 2>} {<1 2 0> <1 2 2>}}
The second is a little bit trickier. Here you could define a PointConfiguration using your input points (via $pc=new PointConfiguration(POINTS=>[[...]]) and read out the edges of the convex hull (using $pc->CONVEX_HULL->EDGES). However, the indices refer to the list of vertices of the convex hull, so you have to use the property $pc->VERTEX_POINT_MAP to map the indices back to the indices of the list of POINTS.

Note that asking for $pc->GRAPH->EDGES for a PointConfiguration, which might look more straightforward, might not return what you want if your list of points contains points on an edge of the convex hull that are not a vertex.

Isaac
Posts: 5
Joined: 29 Sep 2014, 21:03

Re: Is X an edge of the polytope Y?

Postby Isaac » 01 Oct 2014, 02:35

Hi,


Thanks for your reply. Polymake does indeed solve the problem but I am wondering is there a quicker way. With polymake I have to index the vertices and check the edge set manually. Is it true that when polymake outputs the VERTICES e.g.

1 0 2 0 0 0 0 0 0 0 0 0 0 0 0 1 1

1 0 1 0 0 0 1 0 0 0 0 1 0 0 0 0 1

1 0 1 0 0 0 1 0 0 0 0 0 1 0 0 1 0

1 0 0 0 0 0 0 0 2 1 1 0 0 0 0 0 0

1 0 0 0 0 0 1 0 1 0 1 1 0 0 0 0 0

then it indexes them from top down as 0,1,2, ... etc and when you ask for GRAPH->EDGES polymake uses this indexing in the output e.g. {0,1},{0,2},... etc ??

My problem is that if there are e.g. 50 vertices, then finding the index number of two of them manually is time-consuming. Updated question is at

http://math.stackexchange.com/questions ... tope-convf


Thanks again


Isaac

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

Re: Is X an edge of the polytope Y?

Postby paffenholz » 01 Oct 2014, 09:43

Yes, indexing in polymake is always consistent. So the indices in the GRAPH correspond to the list of VERTICES in this order. You can print the index alongside the vertices by using rows_numbered($p->VERTICES).

From what you write it seems you want to work with the vectors itself though. You can ask for containment of a specific pair eg via

Code: Select all

$x=new Set<Vector>($c->VERTICES->[0],$c->VERTICES->[1]); print $a->contains($x);
which will print a "1" if $x is a pair of vertices forming an edge and nothing otherwise. Of course, instead of referencing the vertices you can feed vectors directly, like

Code: Select all

$x=new Set<Vector>([1,0,0],[1,2,0]); print $a->contains($x);

Isaac
Posts: 5
Joined: 29 Sep 2014, 21:03

Re: Is X an edge of the polytope Y?

Postby Isaac » 01 Oct 2014, 17:38

Hi,


That code is exactly what I'm looking for, thanks!! However when I type


$a=new Set<Set<Vector>>; foreach $e (@{$c->GRAPH->EDGES}) { $a+=new Set<Vector>(map ($c->VERTICES->[$_],@{$e})); }

I get the following ERROR message:

ERROR: reference to an undeclared variable $e at input line 1.


All the other pieces of code work perfectly. What's the problem with this one?


Thanks in advance,



Isaac

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

Re: Is X an edge of the polytope Y?

Postby paffenholz » 01 Oct 2014, 17:44

Sorry. There is a "my" missing in front of the $e, so it should read "foreach my $e (@{$c->GRAPH->EDGES}) {...}"

Isaac
Posts: 5
Joined: 29 Sep 2014, 21:03

Re: Is X an edge of the polytope Y?

Postby Isaac » 01 Oct 2014, 18:50

It works perfectly now.

Thanks again for all your help.

User avatar
gawrilow
Main Author
Posts: 422
Joined: 25 Dec 2010, 17:40

Re: Is X an edge of the polytope Y?

Postby gawrilow » 02 Oct 2014, 13:38

$a+=new Set<Vector>(map ($c->VERTICES->[$_],@{$e}));
Just for perl aesthets ;-) :
mapping an index range to array elements can be abbreviated as:

Code: Select all

$a+=new Set<Vector>( @{$c->VERTICES} [@{$e}] );


Return to “General Discussion”