Sage: Ticket #21950: Add pulling_triangulation method to polyhedron class and point configuration
https://trac.sagemath.org/ticket/21950
<p>
A pulling triangulation of a compact polyhedron (a polytope) is obtained recursively.
</p>
<p>
The pulling triangulation of a simplex is the simplex itself.
</p>
<p>
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.
</p>
<p>
This should be done more generally into the Point configuration class.
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/21950
Trac 1.1.6jipilabWed, 23 Nov 2016 14:52:59 GMTtype changed
https://trac.sagemath.org/ticket/21950#comment:1
https://trac.sagemath.org/ticket/21950#comment:1
<ul>
<li><strong>type</strong>
changed from <em>PLEASE CHANGE</em> to <em>enhancement</em>
</li>
</ul>
TicketjipilabWed, 23 Nov 2016 14:53:20 GMTcomponent changed
https://trac.sagemath.org/ticket/21950#comment:2
https://trac.sagemath.org/ticket/21950#comment:2
<ul>
<li><strong>component</strong>
changed from <em>PLEASE CHANGE</em> to <em>geometry</em>
</li>
</ul>
TicketjipilabWed, 23 Nov 2016 15:03:05 GMTkeywords set
https://trac.sagemath.org/ticket/21950#comment:3
https://trac.sagemath.org/ticket/21950#comment:3
<ul>
<li><strong>keywords</strong>
<em>days79</em> <em>triangulation</em> <em>polytope</em> added
</li>
</ul>
TicketmkoeppeWed, 11 Jan 2017 00:44:35 GMTcc, milestone changed
https://trac.sagemath.org/ticket/21950#comment:4
https://trac.sagemath.org/ticket/21950#comment:4
<ul>
<li><strong>cc</strong>
<em>Winfried</em> added
</li>
<li><strong>milestone</strong>
changed from <em>sage-7.5</em> to <em>sage-7.6</em>
</li>
</ul>
<p>
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?
</p>
TicketWinfriedWed, 11 Jan 2017 16:17:19 GMT
https://trac.sagemath.org/ticket/21950#comment:5
https://trac.sagemath.org/ticket/21950#comment:5
<p>
Normaliz usually makes placing = lexicographic triangulations. Note that Normaliz reorders the generators.
</p>
<p>
But there are two potential exceptions:
</p>
<p>
(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.
</p>
<p>
(2) If simplices are subdivided, stellar subdivision is used (and we may actually get a nested triangulation).
</p>
<p>
If you want the lexicographic triangulation with the respect to the input order, then you can force it by
</p>
<p>
<a class="missing wiki">KeepOrder?</a> <a class="missing wiki">NoSubdivision?</a>
</p>
<p>
<a class="missing wiki">KeepOrder?</a> blocks bottom decomposition, so no need for <a class="missing wiki">NoBottomDec?</a>.
</p>
<p>
Usually <a class="missing wiki">KeepOrder?</a> is not a good idea.
</p>
TicketWinfriedWed, 11 Jan 2017 16:18:07 GMT
https://trac.sagemath.org/ticket/21950#comment:6
https://trac.sagemath.org/ticket/21950#comment:6
<p>
Sorry for the question marks ... Not coming from me.
</p>
TicketmkoeppeWed, 11 Jan 2017 19:03:07 GMT
https://trac.sagemath.org/ticket/21950#comment:7
https://trac.sagemath.org/ticket/21950#comment:7
<p>
Thanks a lot, Winfried!
</p>
TicketmkoeppeWed, 11 Jan 2017 19:18:47 GMT
https://trac.sagemath.org/ticket/21950#comment:8
https://trac.sagemath.org/ticket/21950#comment:8
<p>
Jean-Philippe, <code>PointConfiguration</code> already has a method <code>lexicographic_triangulation</code> which according to its documentation computes "the" lexicographic triangulation; I think this is the pulling triangulation (didn't check), as there is another method <code>placing_triangulation</code>, which gives different results.
</p>
<p>
I think the interface of <code>PointConfiguration.triangulate</code> and of <code>Polyhedron.triangulate</code> 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.
</p>
TicketjipilabWed, 11 Jan 2017 20:35:51 GMT
https://trac.sagemath.org/ticket/21950#comment:9
https://trac.sagemath.org/ticket/21950#comment:9
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/21950#comment:8" title="Comment 8">mkoeppe</a>:
</p>
<blockquote class="citation">
<p>
Jean-Philippe, <code>PointConfiguration</code> already has a method <code>lexicographic_triangulation</code> which according to its documentation computes "the" lexicographic triangulation; I think this is the pulling triangulation (didn't check), as there is another method <code>placing_triangulation</code>, which gives different results.
</p>
</blockquote>
<p>
Yes, after some doc_search I found that placing_triangulation which should also be the "pushing" triangulation if I understand correctly.
</p>
<blockquote class="citation">
<p>
I think the interface of <code>PointConfiguration.triangulate</code> and of <code>Polyhedron.triangulate</code> 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.
</p>
</blockquote>
<p>
+1, this is a good idea.
</p>
<p>
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 <a class="missing wiki">PointConfiguration?</a> 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.
</p>
<p>
I plan to work on this during the upcoming <a class="missing wiki">SageDays?</a>.
</p>
TicketjipilabThu, 02 Mar 2017 17:57:00 GMTkeywords changed
https://trac.sagemath.org/ticket/21950#comment:10
https://trac.sagemath.org/ticket/21950#comment:10
<ul>
<li><strong>keywords</strong>
<em>days84</em> added
</li>
</ul>
TicketyzhTue, 30 Mar 2021 15:56:27 GMTcc changed
https://trac.sagemath.org/ticket/21950#comment:11
https://trac.sagemath.org/ticket/21950#comment:11
<ul>
<li><strong>cc</strong>
<em>yzh</em> added
</li>
</ul>
TicketWinfriedTue, 30 Mar 2021 16:21:38 GMT
https://trac.sagemath.org/ticket/21950#comment:12
https://trac.sagemath.org/ticket/21950#comment:12
<p>
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).
</p>
TicketWinfriedWed, 31 Mar 2021 08:47:49 GMT
https://trac.sagemath.org/ticket/21950#comment:13
https://trac.sagemath.org/ticket/21950#comment:13
<p>
Could you provide a precise definition of pulling triangulation?
</p>
Ticket