Computing one interior lattice points of possibly unbounded polytopes
Posted: 09 Mar 2020, 16:58
Sorry for the possibly stupid question, but is there a fast way to compute a single interior lattice point of a possibly unbounded polyhedron in polymake? Preferably of small (ideally minimal) L1-norm.
I know that I can
1. make it bounded by intersecting it with a dilated cube,
2. enumerate all interior lattice points using ->INTERIOR_LATTICE_POINTS,
but that can take quite some time in high ambient dimension and if the bound is not chosen wisely.
For example, the following code is trying to find an interior point of $lsc33, which yields a plane tropical curve of bi-degree (3,3) dual to a honeycomb subdivision with prescribed edge lengths.
I know that I can
1. make it bounded by intersecting it with a dilated cube,
2. enumerate all interior lattice points using ->INTERIOR_LATTICE_POINTS,
but that can take quite some time in high ambient dimension and if the bound is not chosen wisely.
For example, the following code is trying to find an interior point of $lsc33, which yields a plane tropical curve of bi-degree (3,3) dual to a honeycomb subdivision with prescribed edge lengths.
Code: Select all
application "fan";
$M33 = new Matrix([[1,0,0],[1,1,0],[1,2,0],[1,3,0],
[1,0,1],[1,1,1],[1,2,1],[1,3,1],
[1,0,2],[1,1,2],[1,2,2],[1,3,2],
[1,0,3],[1,1,3],[1,2,3],[1,3,3]]);
$C33 = new Array<Set<Int>>([[0,1,4],[1,2,5],[2,3,6],
[1,4,5],[2,5,6],[3,6,7],
[4,5,8],[5,6,9],[6,7,10],
[5,8,9],[6,9,10],[7,10,11],
[8,9,12],[9,10,13],[10,11,14],
[9,12,13],[10,13,14],[11,14,15]]);
$HC33 = new SubdivisionOfPoints(POINTS=>$M33, MAXIMAL_CELLS=>$C33); # honeycomb
$sc33 = $HC33->secondary_cone();
$Rh = zero_vector($sc33->N_RAYS)|$sc33->RAYS;
$Rh = unit_vector($Rh->cols,0)/$Rh;
$Lh = zero_vector($sc33->LINEALITY_DIM)|$sc33->LINEALITY_SPACE;
$sc33 = new Polytope(POINTS=>$Rh, INPUT_LINEALITY=>$Lh); # homogenized sc33
$l = new Matrix([[1, 0, 0,-1, 0, 0, 1, 1, 0, 0,-1, 0, 0, 0, 0, 0, 0],
[3, 0, 0, 0, 0, 0, 1,-1, 0,-1, 1, 0, 0, 0, 0, 0, 0],
[5, 0, 0, 0, 0, 0,-1, 1, 0, 0, 1,-1, 0, 0, 0, 0, 0],
[2, 0, 0, 0, 0, 0, 0,-1, 0, 0, 1, 1, 0, 0,-1, 0, 0],
[6, 0, 0, 0, 0, 0, 0, 1,-1, 0,-1, 1, 0, 0, 0, 0, 0]]);
$L = new Polytope(INEQUALITIES=>[], EQUATIONS=>$l); # encodes fixed edge lengths
$lsc33 = intersection($sc33,$L);
$bsc33 = intersection($lsc33,scale(Polytope::cube($lsc33->AMBIENT_DIM),9));
print $bsc33->N_INTERIOR_LATTICE_POINTS;