Opened 5 years ago
Last modified 6 months 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: |
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 5 years ago by
- Type changed from PLEASE CHANGE to enhancement
comment:2 Changed 5 years ago by
- Component changed from PLEASE CHANGE to geometry
comment:3 Changed 5 years ago by
- Keywords days79 triangulation polytope added
comment:4 Changed 5 years ago by
- Cc Winfried added
- Milestone changed from sage-7.5 to sage-7.6
comment:5 Changed 5 years ago by
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? blocks bottom decomposition, so no need for NoBottomDec?.
Usually KeepOrder? is not a good idea.
comment:6 Changed 5 years ago by
Sorry for the question marks ... Not coming from me.
comment:7 Changed 5 years ago by
Thanks a lot, Winfried!
comment:8 follow-up: ↓ 9 Changed 5 years ago by
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 5 years ago by
Replying to mkoeppe:
Jean-Philippe,
PointConfiguration
already has a methodlexicographic_triangulation
which according to its documentation computes "the" lexicographic triangulation; I think this is the pulling triangulation (didn't check), as there is another methodplacing_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 ofPolyhedron.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 5 years ago by
- Keywords days84 added
comment:11 Changed 6 months ago by
- Cc yzh added
comment:12 Changed 6 months ago by
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 6 months ago by
Could you provide a precise definition of pulling triangulation?
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?