Implement stacking onto a face of a polyhedron

[jplab]

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.

Depends on #22572

CC: @videlec @mo271 @mkoeppe @fchapoton

Component: geometry

Keywords: days93, polytope

Author: Jean-Philippe Labbé

Branch/Commit: e5838ed

Reviewer: Moritz Firsching, Frédéric Chapoton

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

[jplab]

comment:1

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

[jplab]

Dependencies: #22572

[jplab]

Commit: 3bfb953

[jplab]

Branch: u/jipilab/24847

[sagetrac-git]

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

d5908a5

Cleaned two old deprecation warnings

[sagetrac-git]

Changed commit from 3bfb953 to d5908a5

[jplab]

Author: Jean-Philippe Labbé

[sagetrac-git]

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

9677be7

Merge branch '8.2.b7' into 24847

[sagetrac-git]

Changed commit from d5908a5 to 9677be7

[mo271]

Changed branch from u/jipilab/24847 to u/moritz/24847

[sagetrac-git]

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

7f0af17

pep

[sagetrac-git]

Changed commit from 9677be7 to 7f0af17

[mo271]

comment:7

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?

[jplab]

comment:8

Replying to @mo271:

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.

[mo271]

comment:9

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?

[mo271]

Reviewer: Moritz Firsching

[jplab]

comment:11

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.

[jplab]

New commits:

664df99

deal with unbounded faces

[jplab]

Changed commit from 7f0af17 to 664df99

[jplab]

Changed branch from u/moritz/24847 to public/stackpoly

[sagetrac-git]

Changed commit from 664df99 to 2a59f67

[sagetrac-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

[jplab]

comment:14

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.

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

Needs review again!

[fchapoton]

comment:15

branch does not merge

[sagetrac-git]

Changed commit from 2a59f67 to e5838ed

[sagetrac-git]

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

e5838ed

Merge branch 'stackpoly' into 24847

[jplab]

comment:18

Now merges cleanly.

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

[fchapoton]

Changed reviewer from Moritz Firsching to Moritz Firsching, Frédéric Chapoton

[fchapoton]

comment:20

ok, let it be

[jplab]

comment:21

Thanks for the review!

[videlec]

comment:22

update milestone 8.3 -> 8.4

[vbraun]

Changed branch from public/stackpoly to e5838ed