Sage Days 128

During the Sage Days 128 in Le Teich, I worked on the implementation of a function that I wanted to have in Sage for a long time!

Add deformation cones and checking for regularity for Point Configurations and normal fans of Polyhedra #39496

This functionalities are available in Sage version 10.6+.

You can check whether a (full-dimensional) fan is polytopal:

sage: def mother(epsilon=0):
....:     rays = [(4-epsilon,epsilon,0),(0,4-epsilon,epsilon),(epsilon,0,4-epsilon),(2,1,1),(1,2,1),(1,1,2),(-1,-1,-1)]
....:     L = [(0,1,4),(0,3,4),(1,2,5),(1,4,5),(0,2,3),(2,3,5),(3,4,5),(6,0,1),(6,1,2),(6,2,0)]
....:     S1 = [Cone([rays[i] for i in indices]) for indices in L]
....:     return Fan(S1)

When epsilon=0, it is not polytopal:

sage: epsilon = 0
sage: mother(epsilon).is_polytopal()
False

Doing a slight perturbation makes the same subdivision polytopal:

sage: epsilon = 1/2
sage: mother(epsilon).is_polytopal()
True

You can also obtain the deformation cone of a polytope using this functionality. The deformation cone provides the cone of so-called "right-hand-sides" of the H-representation of the starting polytope which provide a deformed polytope whose normal fan coarsens that of the starting polytope. The interior direction of the deformation cone provide the deformation of the polytope that preserve the normal fan (i.e. the space of all the normally equivalent polytopes). The output format follows the order of the normals of the starting polytope and it is not quotiented by the linear transformations (since the output would not be canonical, we run into representations issues here...).

Let's examine the deformation cone of the square with one truncated vertex:

sage: tc = Polyhedron([(1, -1), (1/3, 1), (1, 1/3), (-1, 1), (-1, -1)])
sage: dc = tc.deformation_cone()
sage: dc.an_element()
(2, 1, 1, 0, 0)
sage: [_.A() for _ in tc.Hrepresentation()]
[(1, 0), (0, 1), (0, -1), (-3, -3), (-1, 0)]
sage: P = Polyhedron(rays=[(1, 0, 2), (0, 1, 1), (0, -1, 1), (-3, -3, 0), (-1, 0, 0)])
sage: P.rays()
(A ray in the direction (-1, -1, 0),
 A ray in the direction (-1, 0, 0),
 A ray in the direction (0, -1, 1),
 A ray in the direction (0, 1, 1),
 A ray in the direction (1, 0, 2))

Now, let's compute the deformation cone of the pyramid over a square and verify that it is not full dimensional:

sage: py = Polyhedron([(0, -1, -1), (0, -1, 1), (0, 1, -1), (0, 1, 1), (1, 0, 0)])
sage: dc_py = py.deformation_cone(); dc_py
A 4-dimensional polyhedron in QQ^5 defined as the convex hull of 1 vertex, 1 ray, 3 lines
sage: [ineq.b() for ineq in py.Hrepresentation()]
[0, 1, 1, 1, 1]
sage: r = dc_py.rays()[0]
sage: l1,l2,l3 = dc_py.lines()
sage: r.vector()-l1.vector()/2-l2.vector()-l3.vector()/2
(0, 1, 1, 1, 1)

This function uses the Gale transform as described in Section 5.4 of the Triangulations' book of De Loera-Rambau-Santos.