Opened 4 years ago
Closed 4 years ago
#22498 closed enhancement (fixed)
Add .normal_fan() and .face_fan() methods for rational bounded polyhedra
Reported by:  jipilab  Owned by:  

Priority:  major  Milestone:  sage7.6 
Component:  geometry  Keywords:  geometry, days84, polytope, fan 
Cc:  moritz, mkoeppe, vdelecroix, tmonteil, chapoton  Merged in:  
Authors:  JeanPhilippe Labbé  Reviewers:  Andrey Novoseltsev 
Report Upstream:  N/A  Work issues:  examples 
Branch:  b5c49e6 (Commits, GitHub, GitLab)  Commit:  b5c49e6ec798b08ad4a9659791d7d80433919518 
Dependencies:  Stopgaps: 
Description (last modified by )
This ticket provides the method constructing the normal fan and face fan of a rational bounded polyhedra via the sage.geometry.fan.RationalPolyhedralFan
class.
The normal fan of a polyhedra consists of a set of polyhedral cones indexed by the faces of the polyhedra. Given a face F of a polyhedron, the cone associated to F consists of all the normal vectors of the hyperplanes (linear functions) that are maximal on F. The normal fan has the property that intersections of cones correspond to the intersection of faces.
The face fan is the "dual" construction. Taking a point in the interior of the polytope, the cones of the fan are the positive span of the faces.
All that is done right now is to wrap the methods from sage.geometry.fan.RationalPolyhedralFan
. Eventually, one may consider looking how this could be done using the normaliz backend of polyhedra, if it ever makes sense. This could be done in a separated ticket.
Change History (17)
comment:1 followup: ↓ 2 Changed 4 years ago by
comment:2 in reply to: ↑ 1 Changed 4 years ago by
 Status changed from new to needs_info
sage: NormalFan?(p) Rational polyhedral fan in 3d lattice N }}}
Wow! This is great! Thank you for the reply.
Okay, perhaps I should have asked how to do this first. Then, I suggest to modify the description of the ticket to make this feature apparent in the documentation of Polyhedron. Perhaps also to add a wrapper method in the base class of polyhedron? Is that reasonable?
comment:3 followup: ↓ 4 Changed 4 years ago by
I think adding a method would be great (perhaps with .face_fan()
as well):
 visibility in documentation
 visibility in TABcompletion
 more chances to have tests specifically for
Polyhedron
Of course, all this method should do is return NormalFan(self)
for consistency (can be cached if you wish).
comment:4 in reply to: ↑ 3 Changed 4 years ago by
Of course, all this method should do is
return NormalFan(self)
for consistency (can be cached if you wish).
Yep. Sounds good.
Would it make sense to deprecate NormalFan
and FaceFan
from the global name space then? I do not see a reason not to.
comment:5 followup: ↓ 6 Changed 4 years ago by
NormalFan
and FaceFan
accept other kinds of input as well (in particular LatticePolytope
), and what's the problem with keeping them there? All functions can be recast as methods, but it is not a reason to stop using them at all ;)
comment:6 in reply to: ↑ 5 ; followup: ↓ 10 Changed 4 years ago by
Replying to novoselt:
NormalFan
andFaceFan
accept other kinds of input as well (in particularLatticePolytope
),
Fair enough. At some point I should learn the subtleties between a general Polyhedron object and a LatticePolytope? object... I am currently working on a thematic tutorial and I'd like to know about the differences (I will put you in cc in the ticket once I have something).
and what's the problem with keeping them there? All functions can be recast as methods, but it is not a reason to stop using them at all ;)
Well, if these functions would have been methods of polyhedron, I would have known about them a bit earlier. hehe! Are there other interesting functions like these that are not wrapped as methods?
comment:7 Changed 4 years ago by
 Branch set to u/jipilab/22498
comment:8 Changed 4 years ago by
 Commit set to b13f5958fbc1b090342583b1bb819cc93507aa70
 Description modified (diff)
 Status changed from needs_info to needs_review
 Summary changed from Add .normal_fan() method for polyhedra to Add .normal_fan() and .face_fan() methods for rational bounded polyhedra
comment:9 followup: ↓ 12 Changed 4 years ago by
 Reviewers set to Andrey Novoseltsev
 Status changed from needs_review to needs_work
 Work issues set to examples
There are no examples!!!
Also, is it really necessary to have fulldimensional polytope for the face fan?
comment:10 in reply to: ↑ 6 Changed 4 years ago by
Replying to jipilab:
Replying to novoselt:
NormalFan
andFaceFan
accept other kinds of input as well (in particularLatticePolytope
),Fair enough. At some point I should learn the subtleties between a general Polyhedron object and a LatticePolytope? object... I am currently working on a thematic tutorial and I'd like to know about the differences (I will put you in cc in the ticket once I have something).
The main subtlety is history: 10 years ago cdd was use for Polyhedron with float components and LatticePolytope? was using PALP for integer components. Also in terms of focus Polyhedron was for everything while PALP is written with reflexive polytopes in mind and has some sensible hardcoded limitations that are not sensible at all in general setting (like no dimension above 6 and no more than 64 vertices). Both used to rely on file inputoutput for communication which has huge overhead for small cases, then Cone/Fan? started using Volker's PPL library interface and eventually Polyhedron got fast backends as well while LatticePolytope? was lagging behind. Over the last few years I made incompatible changes (with deprecation periods mostly) to make it close in spirit to Cone and if my recent tickets get merged it will be as fast as Cone apart from point enumeration (which is sort of not a problem fro cones at all, they usually have infinitely many points).
and what's the problem with keeping them there? All functions can be recast as methods, but it is not a reason to stop using them at all ;)
Well, if these functions would have been methods of polyhedron, I would have known about them a bit earlier. hehe! Are there other interesting functions like these that are not wrapped as methods?
Fair enough and no other interesting functions come to mind ;)
comment:11 Changed 4 years ago by
 Commit changed from b13f5958fbc1b090342583b1bb819cc93507aa70 to 16648a857b2e1366e2cab37c6f30b9d48da58474
comment:12 in reply to: ↑ 9 Changed 4 years ago by
Replying to novoselt:
There are no examples!!!
I added examples to both functions and a test for rational coordinates.
It seems that there is no direct test for unboundedness in face fan:
sage: Q = Polyhedron(rays = [[1, 1/2], [1, 1/2]]) sage: Q.face_fan() Traceback (most recent call last): ... ValueError: face fans are defined only for polytopes containing the origin as an interior point! sage: FaceFan(Q) # The currently implemented function Traceback (most recent call last): ... ValueError: face fans are defined only for polytopes containing the origin as an interior point!
That should be treated in a different ticket I guess?
Also, is it really necessary to have fulldimensional polytope for the face fan?
Currently it seems to work:
sage: S = Polyhedron(vertices = [[1, 1/2], [1, 1/2]]) sage: S A 1dimensional polyhedron in QQ^2 defined as the convex hull of 2 vertices sage: FaceFan(S) Rational polyhedral fan in 2d lattice M
comment:13 Changed 4 years ago by
 Commit changed from 16648a857b2e1366e2cab37c6f30b9d48da58474 to b5c49e6ec798b08ad4a9659791d7d80433919518
Branch pushed to git repo; I updated commit sha1. New commits:
b5c49e6  Corrected doc of face_fan

comment:14 Changed 4 years ago by
 Status changed from needs_work to needs_review
comment:15 Changed 4 years ago by
 Status changed from needs_review to positive_review
comment:16 Changed 4 years ago by
Great! Thanks!
comment:17 Changed 4 years ago by
 Branch changed from u/jipilab/22498 to b5c49e6ec798b08ad4a9659791d7d80433919518
 Resolution set to fixed
 Status changed from positive_review to closed