Constructing half integer polytopes

Questions and problems about using polymake go here.
maudi
Posts: 7
Joined: 07 Feb 2011, 18:29

Constructing half integer polytopes

Postby maudi » 16 May 2011, 19:23

Dear all,

I could need your help with constructing half-integer polytopes.

I am generating all 2, 3 and 4 dimensional polytopes whose vertices are element of {0,1/2,1}.
I already constructed a tarball with polytopes of all possible options combining 0, ½ and 1 for dimension 2, 3 and 4. I´ll attach the tarball for reference.

For my further work only the non-isomorphic polytopes are requested.
That means: If polytope x is a mirrored and/or rotated and/or displaced version of polytope y, then it is equal to polytope y, and polytope x is not needed and can be deleted. E.g. the two polytopes in vertices ([1,0,0],[1,1/2,0],[1,0,1/2]) and ([1,1,1][1,1,1/2][1,1/2,1]) are the same and only one of those two is needed.

In polymake I tried to eliminate all polytopes that have the same number of vertices, the same volume and return 1 at the isomorphic test. But even in dimension 2 not all possibilities were found.

Code: Select all

script("tarballs"); @a=unpack_tarball("zweidim_polytope.tgz"); $count=0; @f = (); @g = (); for ($i=0; $i<466; ++$i){ if ($a[$i]->DIM == $a[$i]->AMBIENT_DIM){ $f[$count]=$a[$i]; $count=$count+1; } } for ($j=0; $j<$count; ++$j){ $f[$j]=conv($f[$j]); } $g[0]=$f[0]; $countg=1; $c=0; for ($j=1; $j<$count; ++$j){ for ($k=0; $k<$countg; ++$k){ if (isomorphic($f[$j],$g[$k])==1){ if ($f[$j]->VOLUME==$g[$k]->VOLUME){ if ($f[$j]->N_VERTICES==$g[$k]->N_VERTICES){ $c=1; } } } } if ($c==0){ $g[$countg]=$f[$j]; $countg=$countg+1; } $c=0; } pack_tarball("konvex_2_dim.tgz",@g);
I know that the isomorphic test has to be improved, but I do not know how to do this. I am unfortunately not used to C++.

Maybe (hopefully ;) ) there is an easier way, that I forgot to think of.

I hope anyone can help me with that.

Many thanks,

Mandy
Attachments
zweidim_polytope.tgz
(13.66 KiB) Downloaded 490 times

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

Re: Constructing half integer polytopes

Postby paffenholz » 20 May 2011, 19:47

The function "isomorphic" checks for combinatorial isomorphism, so the check for the number of vertices will always evaluate to true. Yet this test removes probably more polytopes than intended.

There is no obvious direct way in polymake to check for affine equivalence. In small (fixed) dimension the easiest way to solve your problem is probably to explicitely list all maps that could identify two of your polytopes (symmetries of the cube combined with some translations) and check them on all pairs of combinatorially isomorphic polytopes. Admittedly not very elegant. For higher dimensions you would have to develop a suitable algorithm first.

maudi
Posts: 7
Joined: 07 Feb 2011, 18:29

Re: Constructing half integer polytopes

Postby maudi » 25 May 2011, 20:22

Thank you for your answer.

So it is much more difficult as I suspected.

I also thought about combining all possible maps before, hoping for a more comfortable solution. So first of all this will be my way to go. Dimension 2 and 3 should be no problem, but dimension 4 is more complex for realizing the rotation.

Would it be an option to use the isomorphic function for application graph after converting the polytopes to graphs?

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

Re: Constructing half integer polytopes

Postby joswig » 26 May 2011, 17:54

Probably you want to classify up to linear or affine automorphisms (which is almost the same). This can be translated into computing automorphisms of certain colored graphs, see Section 3.2 in the following paper:
Bremner, David(3-NB-FC); Dutour Sikiric, Mathieu(CT-IRBO-SOC); Schürmann, Achill(D-MAG)
Polyhedral representation conversion up to symmetries. Polyhedral computation, 45-71,
CRM Proc. Lecture Notes, 48, Amer. Math. Soc., Providence, RI, 2009.


Return to “Helpdesk”