Opened 4 years ago

Last modified 11 days ago

#21950 new enhancement

Add pulling_triangulation method to polyhedron class and point configuration

Reported by: jipilab Owned by:
Priority: major Milestone: sage-7.6
Component: geometry Keywords: days79, triangulation, polytope, days84
Cc: moritz, mkoeppe, vbraun, Winfried, yzh Merged in:
Authors: Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description

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.

Change History (13)

comment:1 Changed 4 years ago by jipilab

  • Type changed from PLEASE CHANGE to enhancement

comment:2 Changed 4 years ago by jipilab

  • Component changed from PLEASE CHANGE to geometry

comment:3 Changed 4 years ago by jipilab

  • Keywords days79 triangulation polytope added

comment:4 Changed 4 years ago by mkoeppe

  • Cc Winfried added
  • Milestone changed from sage-7.5 to sage-7.6

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?

comment:5 Changed 4 years ago by Winfried

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.

comment:6 Changed 4 years ago by Winfried

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

comment:7 Changed 4 years ago by mkoeppe

Thanks a lot, Winfried!

comment:8 follow-up: Changed 4 years ago by 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.

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.

comment:9 in reply to: ↑ 8 Changed 4 years ago by jipilab

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

comment:10 Changed 4 years ago by jipilab

  • Keywords days84 added

comment:11 Changed 12 days ago by yzh

  • Cc yzh added

comment:12 Changed 12 days ago by Winfried

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

comment:13 Changed 11 days ago by Winfried

Could you provide a precise definition of pulling triangulation?

Note: See TracTickets for help on using tickets.