Implement stacking onto a face of a polyhedron

[jipilab]

From ​https://www.csun.edu/~ctoth/Handbook/chap15.pdf:

Stacking onto a face of a polytope adds a vertex slightly outside of the polytope positioned over a point in the interior of the face.

This is the "polar" of the truncation operation.

[jipilab]

Here's a first working version.

I hesitated between different approaches. This is not the most flexible implementation, but at least a solid enough implementation.

---

New commits:

​3bfb953

first version of stacking

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​d5908a5

Cleaned two old deprecation warnings

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​9677be7

Merge branch '8.2.b7' into 24847

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​7f0af17

pep

[moritz]

That's a nice addition.

One question: Should we give the user more control over the base ring of the resulting stacked polytope? At the moment it quietly changes base ring:

sage: C  = polytopes.cube()
sage: C.base_ring()
Integer Ring
sage: C.stack(C.faces(2)[2], 1/2).base_ring()
Rational Field
sage: C.stack(C.faces(2)[2], 0.5).base_ring()
Real Double Field

Also, in the dual method of face-truncation, there is an option linear_coefficients=None. Should there be an analogous option here?

[jipilab]

Replying to moritz:

That's a nice addition.

Thanks! :)

One question: Should we give the user more control over the base ring of the resulting stacked polytope? At the moment it quietly changes base ring:

sage: C  = polytopes.cube()
sage: C.base_ring()
Integer Ring
sage: C.stack(C.faces(2)[2], 1/2).base_ring()
Rational Field
sage: C.stack(C.faces(2)[2], 0.5).base_ring()
Real Double Field

I do not think it is a good idea. The above is consistent with the Polyhedron constructor and also the current behavior for scaling (and many other methods...):

sage: C = polytopes.cube()
sage: 1/2*C
A 3-dimensional polyhedron in QQ^3 defined as the convex hull of 8 vertices
sage: 0.5*C
A 3-dimensional polyhedron in RDF^3 defined as the convex hull of 8 vertices

The user should be aware of the type of inputs that are given, and the constructed object is somehow expected to be in the fraction field of the ring. The base_ring of self can not be kept in general and if the user wants to keep the base ring, it should keep the input to be in the base ring...

I agree that it would be nice to make this step for the user, but it is a nightmare to implement in a uniform stable way... :-/

Also, in the dual method of face-truncation, there is an option linear_coefficients=None. Should there be an analogous option here?

I thought about it, but it leads to a lot of case analysis. At least, I did not find a simple way to do this. it seems to me that the dual equivalent has more "accessible" freedom than that one. Although I may be wrong.

[moritz]

ok, I agree with your reasoning above.

One more thing:

The stacking seems to work nicely for unbounded polyhedra if you stack on bounded faces of them:

sage: [fac] =  [_ for _ in P.faces(1) if _.as_polyhedron().is_compact()]
sage: P = Polyhedron(ieqs = [[-1,1,0], [1,0,-1], [1,0,1]])
sage: [fac] =  [_ for _ in P.faces(1) if _.as_polyhedron().is_compact()]
sage: P = Polyhedron(ieqs = [[-1,1,0], [1,0,-1], [1,0,1]]); P
A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 2 vertices and 1 ray
sage: [fac] =  [_ for _ in P.faces(1) if _.as_polyhedron().is_compact()]
sage: SP = P.stack(fac); SP
A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 3 vertices and 1 ray
sage: P.vertices(), SP.vertices()
((A vertex at (1, 1), A vertex at (1, -1)),
 (A vertex at (0, 0), A vertex at (1, -1), A vertex at (1, 1)))

Could you add this as an example?

What is the desired behavior when stacking on unbounded faces of unbounded polyhedra?

[jipilab]

The stacking seems to work nicely for unbounded polyhedra if you stack on bounded faces of them:

sage: [fac] =  [_ for _ in P.faces(1) if _.as_polyhedron().is_compact()]
sage: P = Polyhedron(ieqs = [[-1,1,0], [1,0,-1], [1,0,1]])
sage: [fac] =  [_ for _ in P.faces(1) if _.as_polyhedron().is_compact()]
sage: P = Polyhedron(ieqs = [[-1,1,0], [1,0,-1], [1,0,1]]); P
A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 2 vertices and 1 ray
sage: [fac] =  [_ for _ in P.faces(1) if _.as_polyhedron().is_compact()]
sage: SP = P.stack(fac); SP
A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 3 vertices and 1 ray
sage: P.vertices(), SP.vertices()
((A vertex at (1, 1), A vertex at (1, -1)),
 (A vertex at (0, 0), A vertex at (1, -1), A vertex at (1, 1)))

Could you retrieve the first P above? It seems to be missing.

Could you add this as an example?

Sure!

What is the desired behavior when stacking on unbounded faces of unbounded polyhedra?

If one takes "stacking" as adding a vertex "just outside" a face as a definition, then it is not very difficult to extend it to unbounded faces using .representative_point() for face.as_polyhedron() and pushing it out a little.

[jipilab]

New commits:

​664df99

deal with unbounded faces

[git]

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

​7f5e125	fixed typos in polyhedra_quickref.rst
​bd6c356	LateX -> LaTeX in polytope_tikz.rst
​b1ce45b	Several other corrections
​d526f70	renamed tutorial files
​d7896f8	Merge branch 'develop' into 22572
​597b802	Merge branch sage8.2.rc1 into 22572
​eee533a	Corrections from review
​b74ae85	Made tests pass
​b5470d8	Merge branch tutorial into stackpoly
​2a59f67	Added stack to quickref

[jipilab]

I made the function a bit more robust: checking if the face is a PolyhedronFace object, and fixed it so that it accepts unbounded faces.

@moritz: I think that the new examples show the possibilities properly.

Needs review again!

[chapoton]

branch does not merge

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​e5838ed

Merge branch 'stackpoly' into 24847

[jipilab]

Now merges cleanly.

In the ticket, I also remove two old deprecation warnings...

[chapoton]

ok, let it be

[jipilab]

Thanks for the review!

[vdelecroix]

update milestone 8.3 -> 8.4