Add pulling_triangulation method to polyhedron class and point configuration

[Jean-Philippe Labbé]

A pulling triangulation of a compact polyhedron (a polytope) is obtained recursively.

The pulling triangulation of a simplex is the simplex itself.

Given a linear function L on the ambiant space of the polytope, one triangulates all the facets that do not contain the minimal vertex (with respect to L) by induction on the dimension (with the same linear function L), and "cone it back", i.e. add the minimal vertex to all the simplices of the union of triangulations of the facets to obtain a triangulation of the input polytope.

This should be done more generally into the Point configuration class.

[Matthias Köppe]

Winfried, does normaliz have built-in functionality to compute specific triangulations of a cone or polytope such as the pulling triangulation or other lexicographic triangulations?

[Winfried Bruns]

Normaliz usually makes placing = lexicographic triangulations. Note that Normaliz reorders the generators.

But there are two potential exceptions:

(1) If a bottom decomposition is computed, then each of the bottom facets is triangulated lexicographically with respect to its vertices, the order being the restriction of the "global" order to this subset.

(2) If simplices are subdivided, stellar subdivision is used (and we may actually get a nested triangulation).

If you want the lexicographic triangulation with the respect to the input order, then you can force it by

KeepOrder? NoSubdivision?

KeepOrder? blocks bottom decomposition, so no need for NoBottomDec?.

Usually KeepOrder? is not a good idea.

[Winfried Bruns]

Sorry for the question marks ... Not coming from me.

[Matthias Köppe]

Thanks a lot, Winfried!

[Matthias Köppe]

Jean-Philippe, PointConfiguration already has a method lexicographic_triangulation which according to its documentation computes "the" lexicographic triangulation; I think this is the pulling triangulation (didn't check), as there is another method placing_triangulation, which gives different results.

I think the interface of PointConfiguration.triangulate and of Polyhedron.triangulate should be extended so that one can request a specific triangulation. We might also want a method to compute general lexicographic triangulations (a class that includes the pulling and the placing triangulations) as well as regular triangulations, given a vector of heights.

[Jean-Philippe Labbé]

Replying to mkoeppe:

Jean-Philippe, PointConfiguration already has a method lexicographic_triangulation which according to its documentation computes "the" lexicographic triangulation; I think this is the pulling triangulation (didn't check), as there is another method placing_triangulation, which gives different results.

Yes, after some doc_search I found that placing_triangulation which should also be the "pushing" triangulation if I understand correctly.

I think the interface of PointConfiguration.triangulate and of Polyhedron.triangulate should be extended so that one can request a specific triangulation. We might also want a method to compute general lexicographic triangulations (a class that includes the pulling and the placing triangulations) as well as regular triangulations, given a vector of heights.

+1, this is a good idea.

At first, I was thinking to put directly the method in the Polyhedron class, but I also believe that it is better to have it placed in PointConfiguration? and call it from there. Since it involved a more general implementation than the small function I had implemented for Polyhedron, I did not make a commit yet.

I plan to work on this during the upcoming SageDays?.

[Winfried Bruns]

At present Normaliz is computing placing triangulations (fore good reasons). But it would be possible to add pulling triangulations (the routines actually exist, but they re not accessible right now).

[Winfried Bruns]

Could you provide a precise definition of pulling triangulation?

[Matthias Köppe]

Replying to mkoeppe:

as well as regular triangulations, given a vector of heights.

I've opened #33685 (PointConfiguration, Polyhedron, PolyhedralComplex: Compute regular triangulation/subdivision) for this