Opened 2 years ago

Closed 20 months ago

#24847 closed enhancement (fixed)

Implement stacking onto a face of a polyhedron

Reported by: jipilab Owned by:
Priority: major Milestone: sage-8.4
Component: geometry Keywords: days93, polytope
Cc: vdelecroix, moritz, mkoeppe, chapoton Merged in:
Authors: Jean-Philippe Labbé Reviewers: Moritz Firsching, Frédéric Chapoton
Report Upstream: N/A Work issues:
Branch: e5838ed (Commits) Commit: e5838ed86d3b809a700caee05a1a7121c18e9180
Dependencies: #22572 Stopgaps:

Description (last modified by 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.

Change History (23)

comment:1 Changed 2 years ago by jipilab

  • Branch set to u/jipilab/24847
  • Commit set to 3bfb953c7768ca9d70f49f9fdd8afd0730972d28
  • Dependencies set to #22572
  • Description modified (diff)
  • Status changed from new to needs_review

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:

3bfb953first version of stacking

comment:2 Changed 2 years ago by git

  • Commit changed from 3bfb953c7768ca9d70f49f9fdd8afd0730972d28 to d5908a56214314913019b8a23cbce90b355e1015

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

d5908a5Cleaned two old deprecation warnings

comment:3 Changed 2 years ago by jipilab

  • Authors set to Jean-Philippe Labbé

comment:4 Changed 2 years ago by git

  • Commit changed from d5908a56214314913019b8a23cbce90b355e1015 to 9677be72e86bda92805002a60c8395f0c07b5ec1

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

9677be7Merge branch '8.2.b7' into 24847

comment:5 Changed 2 years ago by moritz

  • Branch changed from u/jipilab/24847 to u/moritz/24847

comment:6 Changed 2 years ago by git

  • Commit changed from 9677be72e86bda92805002a60c8395f0c07b5ec1 to 7f0af175384c559ef091af7c61abc0e1bc07f01f

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

7f0af17pep

comment:7 follow-up: Changed 2 years ago by 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?

comment:8 in reply to: ↑ 7 Changed 2 years ago by 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.

comment:9 follow-up: Changed 2 years ago by 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?

comment:10 Changed 2 years ago by moritz

  • Reviewers set to Moritz Firsching

comment:11 in reply to: ↑ 9 Changed 2 years ago by 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.

comment:12 Changed 2 years ago by jipilab

  • Branch changed from u/moritz/24847 to public/stackpoly
  • Commit changed from 7f0af175384c559ef091af7c61abc0e1bc07f01f to 664df999f6260084f2817bd557ea77d1c31a3d68

New commits:

664df99deal with unbounded faces

comment:13 Changed 2 years ago by git

  • Commit changed from 664df999f6260084f2817bd557ea77d1c31a3d68 to 2a59f674ce2c9da6a79624ebcc4cffa07182422d

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

7f5e125fixed typos in polyhedra_quickref.rst
bd6c356LateX -> LaTeX in polytope_tikz.rst
b1ce45bSeveral other corrections
d526f70renamed tutorial files
d7896f8Merge branch 'develop' into 22572
597b802Merge branch sage8.2.rc1 into 22572
eee533aCorrections from review
b74ae85Made tests pass
b5470d8Merge branch tutorial into stackpoly
2a59f67Added stack to quickref

comment:14 Changed 2 years ago by jipilab

  • Description modified (diff)

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!

comment:15 Changed 21 months ago by chapoton

  • Status changed from needs_review to needs_work

branch does not merge

comment:16 Changed 21 months ago by git

  • Commit changed from 2a59f674ce2c9da6a79624ebcc4cffa07182422d to e5838ed86d3b809a700caee05a1a7121c18e9180

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

e5838edMerge branch 'stackpoly' into 24847

comment:17 Changed 21 months ago by jipilab

  • Milestone changed from sage-8.2 to sage-8.3

comment:18 Changed 21 months ago by jipilab

Now merges cleanly.

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

comment:19 Changed 21 months ago by jipilab

  • Status changed from needs_work to needs_review

comment:20 Changed 21 months ago by chapoton

  • Reviewers changed from Moritz Firsching to Moritz Firsching, Frédéric Chapoton
  • Status changed from needs_review to positive_review

ok, let it be

comment:21 Changed 21 months ago by jipilab

Thanks for the review!

comment:22 Changed 20 months ago by vdelecroix

  • Milestone changed from sage-8.3 to sage-8.4

update milestone 8.3 -> 8.4

comment:23 Changed 20 months ago by vbraun

  • Branch changed from public/stackpoly to e5838ed86d3b809a700caee05a1a7121c18e9180
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.