Voronoi Tessellation with "cdd" and "beneath_beyond"

[Burggraf]

Hello,

I started again to work on Voronoi Tessellation with polymake. Right know I am able to get DUAL_GRAPH->ADJACENCY with the "cdd" method with:
my $VD = new VoronoiDiagram(SITES=>[[1,1,1],[1,0,1],[1,-1,1],[1,1,-1],[1,0,-1],[1,-1,-1]]);$VD->DUAL_GRAPH->ADJACENCY;save($VD,”OUTPUT.xml”);
but this solution seems to be very slow for more than 500 data points.

Therefore, I want to switch over to the beneath_beyond method. I changed my command lines to:
my $points=new Matrix<Rational>([[1,-1,-1],[1,1,-1],[1,-1,1],[1,1,1],[1,0,0]]); $p=new Polytope<Rational>(POINTS=>$points); prefer_now "beneath_beyond";$p->DUAL_GRAPH->ADJACENCY; save($p,”OUTPUT.xml”);

But I am not sure, if these lines produces the same output, than the first attempt. Furthermore, the xml files reports, that the "cdd" method was used again. ???

Maybe somebody has a good hint for me.
Thanks and have a good weekend

Timo

[gawrilow]

Are you entering these commands line by line in the interactive shell or are they stored in a script file which you are executing at once? Beware that the effect of prefer_now is very limited in time, namely, all changes are automatically reverted before the next interactive prompt appears.

BTW, in order to know for sure which rules are applied, you should (maybe temporarily) set the variable $Verbose::rules=3;

[Burggraf]

Good morning,
thanks for your quick response.

Right now, i am launching polymake from prompt with Attributes:

polymake 'my $VD = new VoronoiDiagram(SITES=>[[1,1,1],[1,0,1],[1,-1,1],[1,1,-1],[1,0,-1],[1,-1,-1]]);$VD->DUAL_GRAPH->ADJACENCY;save($VD,"OUTPUT.xml");'

or

polymake ‘my $points=new Matrix<Rational>([[1,-1,-1],[1,1,-1],[1,-1,1],[1,1,1],[1,0,0]]); $p=new Polytope<Rational>(POINTS=>$points); prefer_now "beneath_beyond";$p->DUAL_GRAPH->ADJACENCY; save($p,”OUTPUT.xml”);’

I tried to store these commands in a script, but i was not able to make it work.

Thanks a lot
Timo

[joswig]

Ewgenij's recommendation

Code: Select all

polytope > $Verbose::rules=3; polytope > my $points=new Matrix<Rational>([[1,-1,-1],[1,1,-1],[1,-1,1],[1,1,1],[1,0,0]]); $p=new Polytope<Rational>(POINTS=>$points); prefer_now "beneath_beyond";$p->DUAL_GRAPH->ADJACENCY; save($p,"OUTPUT.xml");

results in rather lengthy output (which may be hard to digest):

Code: Select all

polymake: applying rule precondition : exists(INEQUALITIES | EQUATIONS) ( initial : FEASIBLE : ) polymake: WARNING: precondition : exists(INEQUALITIES | EQUATIONS) ( initial : FEASIBLE : ) not satisfied polymake: applying rule precondition : exists(VERTICES | POINTS) ( initial : FEASIBLE : ) polymake: precondition : exists(VERTICES | POINTS) ( initial : FEASIBLE : ) satisfied polymake: applying rule precondition: !exists(FEASIBLE) ( initial : FEASIBLE : ) polymake: precondition: !exists(FEASIBLE) ( initial : FEASIBLE : ) satisfied polymake: applying rule precondition : exists(FACETS) ( initial : FEASIBLE : ) polymake: WARNING: precondition : exists(FACETS) ( initial : FEASIBLE : ) not satisfied polymake: applying rule precondition : exists(RAYS) ( initial : LINEALITY_SPACE : ) polymake: WARNING: precondition : exists(RAYS) ( initial : LINEALITY_SPACE : ) not satisfied polymake: applying rule precondition : exists(FACETS) ( initial : LINEAR_SPAN : ) polymake: WARNING: precondition : exists(FACETS) ( initial : LINEAR_SPAN : ) not satisfied polymake: applying rule precondition : exists(INPUT_LINEALITY) ( initial : INPUT_RAYS : ) polymake: WARNING: precondition : exists(INPUT_LINEALITY) ( initial : INPUT_RAYS : ) not satisfied polymake: applying rule precondition : exists(EQUATIONS) ( initial : INEQUALITIES : ) polymake: WARNING: precondition : exists(EQUATIONS) ( initial : INEQUALITIES : ) not satisfied polymake: applying rule initial : FEASIBLE : polymake: applying rule precondition : FEASIBLE ( lrs.convex_hull.count: N_VERTICES, N_BOUNDED_VERTICES, POINTED, LINEALITY_DIM : FACETS | INEQUALITIES ) polymake: precondition : FEASIBLE ( lrs.convex_hull.count: N_VERTICES, N_BOUNDED_VERTICES, POINTED, LINEALITY_DIM : FACETS | INEQUALITIES ) satisfied polymake: applying rule precondition : FEASIBLE ( lrs.convex_hull.count: N_BOUNDED_VERTICES, POINTED, LINEALITY_DIM : FACETS | INEQUALITIES ) polymake: precondition : FEASIBLE ( lrs.convex_hull.count: N_BOUNDED_VERTICES, POINTED, LINEALITY_DIM : FACETS | INEQUALITIES ) satisfied polymake: applying rule precondition : FEASIBLE ( AFFINE_HULL : CONE_AMBIENT_DIM ) polymake: WARNING: precondition : FEASIBLE ( AFFINE_HULL : CONE_AMBIENT_DIM ) not satisfied polymake: applying rule precondition : RAYS | INPUT_RAYS | LINEALITY_SPACE | INPUT_LINEALITY | INEQUALITIES | FACETS | EQUATIONS | LINEAR_SPAN ( CONE_AMBIENT_DIM : ) polymake: precondition : RAYS | INPUT_RAYS | LINEALITY_SPACE | INPUT_LINEALITY | INEQUALITIES | FACETS | EQUATIONS | LINEAR_SPAN ( CONE_AMBIENT_DIM : ) satisfied polymake: applying rule POINTED : INPUT_RAYS polymake: applying rule precondition : exists(INEQUALITIES | EQUATIONS) ( initial : FEASIBLE : ) polymake: precondition : exists(INEQUALITIES | EQUATIONS) ( initial : FEASIBLE : ) satisfied polymake: applying rule precondition: !exists(FEASIBLE) ( initial : FEASIBLE : ) polymake: precondition: !exists(FEASIBLE) ( initial : FEASIBLE : ) satisfied polymake: applying rule precondition : exists(VERTICES | POINTS) ( initial : FEASIBLE : ) polymake: WARNING: precondition : exists(VERTICES | POINTS) ( initial : FEASIBLE : ) not satisfied polymake: applying rule precondition : exists(FACETS) ( initial : FEASIBLE : ) polymake: WARNING: precondition : exists(FACETS) ( initial : FEASIBLE : ) not satisfied polymake: applying rule precondition : exists(RAYS) ( initial : LINEALITY_SPACE : ) polymake: WARNING: precondition : exists(RAYS) ( initial : LINEALITY_SPACE : ) not satisfied polymake: applying rule precondition : exists(FACETS) ( initial : LINEAR_SPAN : ) polymake: WARNING: precondition : exists(FACETS) ( initial : LINEAR_SPAN : ) not satisfied polymake: applying rule precondition : exists(INPUT_LINEALITY) ( initial : INPUT_RAYS : ) polymake: WARNING: precondition : exists(INPUT_LINEALITY) ( initial : INPUT_RAYS : ) not satisfied polymake: applying rule precondition : exists(EQUATIONS) ( initial : INEQUALITIES : ) polymake: WARNING: precondition : exists(EQUATIONS) ( initial : INEQUALITIES : ) not satisfied polymake: applying rule initial : FEASIBLE : polymake: applying rule precondition : FEASIBLE ( lrs.convex_hull.count: N_VERTICES, N_BOUNDED_VERTICES, POINTED, LINEALITY_DIM : FACETS | INEQUALITIES ) polymake: precondition : FEASIBLE ( lrs.convex_hull.count: N_VERTICES, N_BOUNDED_VERTICES, POINTED, LINEALITY_DIM : FACETS | INEQUALITIES ) satisfied polymake: applying rule precondition : FEASIBLE ( lrs.convex_hull.count: N_BOUNDED_VERTICES, POINTED, LINEALITY_DIM : FACETS | INEQUALITIES ) polymake: precondition : FEASIBLE ( lrs.convex_hull.count: N_BOUNDED_VERTICES, POINTED, LINEALITY_DIM : FACETS | INEQUALITIES ) satisfied polymake: applying rule precondition : RAYS | INPUT_RAYS | LINEALITY_SPACE | INPUT_LINEALITY | INEQUALITIES | FACETS | EQUATIONS | LINEAR_SPAN ( CONE_AMBIENT_DIM : ) polymake: precondition : RAYS | INPUT_RAYS | LINEALITY_SPACE | INPUT_LINEALITY | INEQUALITIES | FACETS | EQUATIONS | LINEAR_SPAN ( CONE_AMBIENT_DIM : ) satisfied polymake: applying rule precondition : FEASIBLE ( AFFINE_HULL : CONE_AMBIENT_DIM ) polymake: WARNING: precondition : FEASIBLE ( AFFINE_HULL : CONE_AMBIENT_DIM ) not satisfied polymake: applying rule CONE_AMBIENT_DIM : polymake: applying rule precondition : CONE_AMBIENT_DIM ( LINEALITY_SPACE : FACETS | INEQUALITIES ) polymake: precondition : CONE_AMBIENT_DIM ( LINEALITY_SPACE : FACETS | INEQUALITIES ) satisfied polymake: applying rule LINEALITY_SPACE : FACETS | INEQUALITIES polymake: applying rule LINEALITY_DIM : LINEALITY_SPACE polymake: applying rule POINTED : LINEALITY_DIM polymake: applying rule precondition : POINTED ( ONE_VERTEX : LP.MINIMAL_VERTEX | LP.MAXIMAL_VERTEX ) polymake: precondition : POINTED ( ONE_VERTEX : LP.MINIMAL_VERTEX | LP.MAXIMAL_VERTEX ) satisfied polymake: applying rule precondition : POINTED ( beneath_beyond.convex_hull.primal, default.triangulation: FACETS, LINEAR_SPAN, RAYS_IN_FACETS, DUAL_GRAPH.ADJACENCY, TRIANGULATION, ESSENTIALLY_GENERIC : RAYS ) polymake: precondition : POINTED ( beneath_beyond.convex_hull.primal, default.triangulation: FACETS, LINEAR_SPAN, RAYS_IN_FACETS, DUAL_GRAPH.ADJACENCY, TRIANGULATION, ESSENTIALLY_GENERIC : RAYS ) satisfied polymake: applying rule precondition : POINTED ( porta.convex_hull.primal: FACETS, AFFINE_HULL : CONE_AMBIENT_DIM, CONE_DIM, VERTICES | POINTS ) polymake: precondition : POINTED ( porta.convex_hull.primal: FACETS, AFFINE_HULL : CONE_AMBIENT_DIM, CONE_DIM, VERTICES | POINTS ) satisfied polymake: applying rule precondition : POINTED ( porta.convex_hull.dual: VERTICES, LINEALITY_SPACE : CONE_AMBIENT_DIM, FACETS | INEQUALITIES, VALID_POINT ) polymake: precondition : POINTED ( porta.convex_hull.dual: VERTICES, LINEALITY_SPACE : CONE_AMBIENT_DIM, FACETS | INEQUALITIES, VALID_POINT ) satisfied polymake: applying rule BOUNDED : FACETS | INEQUALITIES, LINEALITY_SPACE polymake: applying rule precondition : BOUNDED ( graph_from_vertices : GRAPH.ADJACENCY : RAYS ) polymake: WARNING: precondition : BOUNDED ( graph_from_vertices : GRAPH.ADJACENCY : RAYS ) not satisfied polymake: applying rule cdd.simplex: LP.MAXIMAL_VALUE, LP.MAXIMAL_VERTEX, FEASIBLE : LP.LINEAR_OBJECTIVE, FACETS | INEQUALITIES polymake: applying rule precondition : POINTED ( porta.convex_hull.dual: VERTICES, LINEALITY_SPACE : CONE_AMBIENT_DIM, FACETS | INEQUALITIES, VALID_POINT ) polymake: precondition : POINTED ( porta.convex_hull.dual: VERTICES, LINEALITY_SPACE : CONE_AMBIENT_DIM, FACETS | INEQUALITIES, VALID_POINT ) satisfied polymake: applying rule precondition : POINTED ( beneath_beyond.convex_hull.primal, default.triangulation: FACETS, RAYS, LINEAR_SPAN, LINEALITY_SPACE, RAYS_IN_FACETS, DUAL_GRAPH.ADJACENCY, TRIANGULATION_INT : INPUT_RAYS ) polymake: precondition : POINTED ( beneath_beyond.convex_hull.primal, default.triangulation: FACETS, RAYS, LINEAR_SPAN, LINEALITY_SPACE, RAYS_IN_FACETS, DUAL_GRAPH.ADJACENCY, TRIANGULATION_INT : INPUT_RAYS ) satisfied polymake: applying rule precondition : POINTED ( beneath_beyond.convex_hull.primal, default.triangulation: FACETS, LINEAR_SPAN, RAYS_IN_FACETS, DUAL_GRAPH.ADJACENCY, TRIANGULATION, ESSENTIALLY_GENERIC : RAYS ) polymake: precondition : POINTED ( beneath_beyond.convex_hull.primal, default.triangulation: FACETS, LINEAR_SPAN, RAYS_IN_FACETS, DUAL_GRAPH.ADJACENCY, TRIANGULATION, ESSENTIALLY_GENERIC : RAYS ) satisfied polymake: applying rule precondition : POINTED ( cdd.convex_hull.redund: RAYS, RAY_SEPARATORS, LINEALITY_SPACE : INPUT_RAYS ) polymake: precondition : POINTED ( cdd.convex_hull.redund: RAYS, RAY_SEPARATORS, LINEALITY_SPACE : INPUT_RAYS ) satisfied polymake: applying rule precondition : POINTED ( LINEALITY_DIM, LINEALITY_SPACE : ) polymake: precondition : POINTED ( LINEALITY_DIM, LINEALITY_SPACE : ) satisfied polymake: applying rule precondition : POINTED ( porta.convex_hull.primal: FACETS, AFFINE_HULL : CONE_AMBIENT_DIM, CONE_DIM, VERTICES | POINTS ) polymake: precondition : POINTED ( porta.convex_hull.primal: FACETS, AFFINE_HULL : CONE_AMBIENT_DIM, CONE_DIM, VERTICES | POINTS ) satisfied polymake: applying rule CONE_AMBIENT_DIM : polymake: applying rule precondition : CONE_AMBIENT_DIM ( LINEALITY_SPACE : FACETS | INEQUALITIES ) polymake: precondition : CONE_AMBIENT_DIM ( LINEALITY_SPACE : FACETS | INEQUALITIES ) satisfied polymake: applying rule N_INPUT_RAYS : INPUT_RAYS polymake: applying rule precondition : N_RAYS | N_INPUT_RAYS ( cdd.convex_hull.primal: FACETS, LINEAR_SPAN : RAYS | INPUT_RAYS ) polymake: precondition : N_RAYS | N_INPUT_RAYS ( cdd.convex_hull.primal: FACETS, LINEAR_SPAN : RAYS | INPUT_RAYS ) satisfied polymake: applying rule precondition : N_RAYS | N_INPUT_RAYS ( lrs.convex_hull.primal: FACETS, LINEAR_SPAN : RAYS | INPUT_RAYS ) polymake: precondition : N_RAYS | N_INPUT_RAYS ( lrs.convex_hull.primal: FACETS, LINEAR_SPAN : RAYS | INPUT_RAYS ) satisfied polymake: applying rule CONE_DIM : RAYS | INPUT_RAYS polymake: applying rule precondition : CONE_DIM ( porta.convex_hull.primal: FACETS, AFFINE_HULL : CONE_AMBIENT_DIM, CONE_DIM, VERTICES | POINTS ) polymake: precondition : CONE_DIM ( porta.convex_hull.primal: FACETS, AFFINE_HULL : CONE_AMBIENT_DIM, CONE_DIM, VERTICES | POINTS ) satisfied polymake: applying rule FULL_DIM : CONE_AMBIENT_DIM, CONE_DIM polymake: applying rule precondition : FULL_DIM ( LINEAR_SPAN : ) polymake: precondition : FULL_DIM ( LINEAR_SPAN : ) satisfied polymake: applying rule LINEALITY_DIM, LINEALITY_SPACE : polymake: applying rule COMBINATORIAL_DIM : CONE_DIM, LINEALITY_DIM polymake: applying rule precondition : COMBINATORIAL_DIM ( DUAL_GRAPH.ADJACENCY : HASSE_DIAGRAM ) polymake: precondition : COMBINATORIAL_DIM ( DUAL_GRAPH.ADJACENCY : HASSE_DIAGRAM ) satisfied polymake: applying rule BOUNDED : VERTICES | POINTS, POINTED polymake: applying rule precondition : BOUNDED, CONE_AMBIENT_DIM ( jarvis.convex_hull.primal : VERTICES : POINTS ) polymake: precondition : BOUNDED, CONE_AMBIENT_DIM ( jarvis.convex_hull.primal : VERTICES : POINTS ) satisfied polymake: applying rule beneath_beyond.convex_hull.primal, default.triangulation: FACETS, RAYS, LINEAR_SPAN, LINEALITY_SPACE, RAYS_IN_FACETS, DUAL_GRAPH.ADJACENCY, TRIANGULATION_INT : INPUT_RAYS

The interesting information for you is only the very last line (which I repeat here):

Code: Select all

polymake: applying rule beneath_beyond.convex_hull.primal, default.triangulation: FACETS, RAYS, LINEAR_SPAN, LINEALITY_SPACE, RAYS_IN_FACETS, DUAL_GRAPH.ADJACENCY, TRIANGULATION_INT : INPUT_RAYS

So, indeed, polymake does what you want.

However, this shows that two things are to be learned: (1) The verbose output should be re-organized to yield something more readable. While the above output is useful, we need a new output level to show what polymake actually does (not what it tries). The above should maybe be moved to a new level 4. (2) The reason why cdd shows in your output file is that cdd is used to solve a linear program in order to decide whether your input is POINTED. This is correct; you can avoid it by saying

Code: Select all

my $points=new Matrix<Rational>([[1,-1,-1],[1,1,-1],[1,-1,1],[1,1,1],[1,0,0]]); $p=new Polytope<Rational>(POINTS=>$points,POINTED=>1); prefer_now "beneath_beyond";$p->DUAL_GRAPH->ADJACENCY; save($p,"OUTPUT.xml");

This also saves some time.

[Burggraf]

Hello again,

I realized the "beneath_beyond" mode, thanks for the last posts.
But now, I am a little bit confused... (sorry)
I know, that the "beneath_beyond" mode works on the convex hull of a polytope with one additional dimension. I assume that polymake does not do the additional dimenson on it's own, so I add one entry to each homogeneous coordinates like this [1,x0,x1,...,xN,squared(x0,x1,...,xN)].

But this result in :
property name="DUAL_GRAPH"> -<object> -<property name="ADJACENCY"> -<m> <v>1 4 8</v> <v>0 2 9</v> <v>1 6 11</v> <v>4 5 15</v> <v>0 3 10</v> <v>3 7 10</v> <v>2 9 13</v> <v>5 12 14</v> <v>0 11 12</v> <v>1 6 15</v> <v>4 5 12</v> <v>2 8 13</v> <v>7 8 10</v> <v>6 11 14</v> <v>7 13 15</v> <v>3 9 14</v> </m> </property> </object> </property>

Which means, that I get more nearest neighbor information than data points...???

If I dont add the sum of squared value of each component, I get less ADJACENCY than data points...
I am pretty sure, that I did not understand the idea of "beneath_beyond".

Thanks for your patience.

timo

[joswig]

There is one facet per point plus one extra facet for the FAR_FACE (in this case the FAR_FACE is a facet).
But you do not have to worry about lifting.

Code: Select all

polytope > my $points=new Matrix<Rational>([[1,-1,-1],[1,1,-1],[1,-1,1],[1,1,1],[1,0,0]]); $vd=new VoronoiDiagram(SITES=>$points); prefer_now "beneath_beyond";$vd->DUAL_GRAPH->ADJACENCY;

Here you see the numbering of the FACETS (which correspond to the SITES. The last one is the extra facet.

Code: Select all

polytope > print rows_labeled($vd->FACETS); 0:2 2 2 1 1:2 -2 2 1 2:2 2 -2 1 3:2 -2 -2 1 4:0 0 0 1 5:1 0 0 0 polytope > print rows_labeled($vd->DUAL_GRAPH->ADJACENCY); 0:1 2 4 5 1:0 3 4 5 2:0 3 4 5 3:1 2 4 5 4:0 1 2 3 5:0 1 2 3

What you are interested in is the following:

Code: Select all

polytope > print $vd->DELAUNAY_GRAPH->ADJACENCY; {1 2 4} {0 3 4} {0 3 4} {1 2 4} {0 1 2 3}

This is the same as:

Code: Select all

polytope > print induced_subgraph($vd->DUAL_GRAPH->ADJACENCY,new Set([0..4])); {1 2 4} {0 3 4} {0 3 4} {1 2 4} {0 1 2 3}

[Burggraf]

Good Morning,

now everything is working, thanks a lot!
The problem was, that I defined a polytope with the points, not a voronoi Diagram. Now, everything is fine.

Cheers
Timo

[Burggraf]

Hello,

if the far field connection in DUAL_GRAPH->ADJACENCY has a smaller index than number of data point n. I assume that this is a valid connection?

I made a comparison with annother Voronoi algorithm and found these connections missing. My mistake was, that I ignored the extra facet and every far field connection, per definition. I fixed this in my code.

One more point, I was not able to get a different system behavior, e.g. runtime, results. for:

Code: Select all

polymake 'my $VD = new VoronoiDiagram(SITES=>...);$VD->DUAL_GRAPH->ADJACENCY; save($VD,\"OUTPUT.xml\");'

and

Code: Select all

polymake '$Verbose::rules=3;my $points=new Matrix<Rational>(...);my $vd=new VoronoiDiagram(SITES=>$points,POINTED=>1); prefer_now "beneath_beyond";$vd->DUAL_GRAPH->ADJACENCY;save($vd,\"OUTPUT.xml\");'

I thought, that they would differ at least in runtime???
Thanks.
Timo

[gawrilow]

... I tried to store these commands in a script, but i was not able to make it work.

I guess, you have forgotten to start you script with the mandatory command

Code: Select all

use application "polytope";

Please refer to the scripting guide for more details.

[Burggraf]

Hi,

thanks for your last post. You are right, I did not include "use application".

Thanks! I put it in the script file now I am able to start the script with:

Code: Select all

polymake polymake_script.txt