Mapping between faces of triangulation and faces of polytope

Questions and problems about using polymake go here.
vissarion
Posts: 9
Joined: 30 May 2012, 19:01

Mapping between faces of triangulation and faces of polytope

Postby vissarion » 30 May 2012, 19:17

Hello,

I have a question regarding triangulations of point configurations and polytopes in polymake. Assume we have a point configuration $pc and $Q is its convex hull (represented by a polytope) in polymake. For example:

Code: Select all

$pc=new PointConfiguration<Rational> (POINTS=>[[1,0,0],[1,1,2],[1,4,2],[1,2,1]], WEIGHTS=>[0,0,0,-1], WEIGHTS_GENERIC=>1); $Q=new Polytope<Rational>(POINTS=>$pc->POINTS);
Given a face $f of the boundary of the triangulation of $pc I would like to find the unique face $F of $Q, of the same dimension, that $f lies. Then I would like to find all the points of $pc that lie on $F. Is there a simple way to do this in polymake?

Thanks a lot,
Vissarion

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

Re: Mapping between faces of triangulation and faces of poly

Postby paffenholz » 31 May 2012, 00:26

It seems you are using an older version of polymake, as WEIGHTS has been declared as a subproperty of TRIANGULATION in the newest. The following should also work with your version though.

You can access the convex hull of a point configuration $pc from within $pc by asking for its CONVEX_HULL. This property contains the convex hull of $pc is of type polytope, so it has all properties and methods you expect from a usual polytope (e.g. $pc->CONVEX_HULL->FACETS gives the facets). It has one additional property: $pc->CONVEX_HULL->VERTEX_POINT_MAP gives a map that assigns each vertex of the convex hull the index of the corresponding point in $pc->POINTS.

There is, however, no direct solution to your question. You will need some lines of perl within the shell. To find the facet of the convex hull a given set of points is contained in you would have to loop over all facets of $pc->CONVEX_HULL until you find one such that the scalar product of the facet with all points in the face evaluates to 0. The second question is similar: for a given facet loop over all points and store those that are on the facet.

I could suggest some lines of perl for this if wanted.

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

Re: Mapping between faces of triangulation and faces of poly

Postby joswig » 31 May 2012, 09:56

The following is a slight variation/addition to the solution suggested above.

Suppose you have a cube and some triangulation. This induces a triangulation of the boundary.

Code: Select all

$c=cube(3); $t=$c->TRIANGULATION->BOUNDARY;
The following (naive) code checks all pairs of facets from the triangulation and the polytope. Extensions and speed up easily possible.

Code: Select all

foreach my $bnd_triangle (@{$t->FACETS}) { foreach my $poly_facet (@{$c->VERTICES_IN_FACETS}) { print $bnd_triangle, " in ", $poly_facet, "\n" if incl($bnd_triangle,$poly_facet)<0; } }
The output of the latter is:

Code: Select all

{0 1 2} in {0 1 2 3} {0 1 4} in {0 1 4 5} {0 2 4} in {0 2 4 6} {1 2 3} in {0 1 2 3} {1 3 5} in {1 3 5 7} {1 4 5} in {0 1 4 5} {2 3 6} in {2 3 6 7} {2 4 6} in {0 2 4 6} {4 5 6} in {4 5 6 7} {3 5 7} in {1 3 5 7} {3 6 7} in {2 3 6 7} {5 6 7} in {4 5 6 7}
Of course, if you work with a PointConfiguration instead of a Polytope you additionally need to employ CONVEX_HULL and VERTEX_POINT_MAP as indicated above.

vissarion
Posts: 9
Joined: 30 May 2012, 19:01

Re: Mapping between faces of triangulation and faces of poly

Postby vissarion » 31 May 2012, 17:46

Thanks a lot for your quick reply and your suggestions!


Return to “Helpdesk”