Add pulling_triangulation method to polyhedron class and point configuration

[jplab]

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.

CC: @mo271 @mkoeppe @vbraun @w-bruns @yuan-zhou

Component: geometry

Keywords: days79, triangulation, polytope, days84

Issue created by migration from https://trac.sagemath.org/ticket/21950

[jplab]

Changed keywords from none to days79, triangulation, polytope

[mkoeppe]

comment:4

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?

[w-bruns]

comment:5

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.

[w-bruns]

comment:6

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

[mkoeppe]

comment:7

Thanks a lot, Winfried!

[mkoeppe]

comment:8

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.

[jplab]

comment:9

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.

[jplab]

Changed keywords from days79, triangulation, polytope to days79, triangulation, polytope, days84

[w-bruns]

comment:12

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).

[w-bruns]

comment:13

Could you provide a precise definition of pulling triangulation?

[mkoeppe]

comment:14

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