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: sage-7.6
Component: geometry Keywords: geometry, days84, polytope, fan
Cc: moritz, mkoeppe, vdelecroix, tmonteil, chapoton Merged in:
Authors: Jean-Philippe Labbé Reviewers: Andrey Novoseltsev
Report Upstream: N/A Work issues: examples
Branch: b5c49e6 (Commits, GitHub, GitLab) Commit: b5c49e6ec798b08ad4a9659791d7d80433919518
Dependencies: Stopgaps:

Status badges

Description (last modified by jipilab)

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 follow-up: Changed 4 years ago by novoselt

sage: p = polytopes.cube(); p
A 3-dimensional polyhedron in ZZ^3 defined as the convex hull of 8 vertices
sage: NormalFan(p)
Rational polyhedral fan in 3-d lattice N

comment:2 in reply to: ↑ 1 Changed 4 years ago by jipilab

  • Status changed from new to needs_info

sage: NormalFan?(p) Rational polyhedral fan in 3-d 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 follow-up: Changed 4 years ago by novoselt

I think adding a method would be great (perhaps with .face_fan() as well):

  • visibility in documentation
  • visibility in TAB-completion
  • 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 jipilab

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 follow-up: Changed 4 years ago by novoselt

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 ; follow-up: Changed 4 years ago by jipilab

Replying to novoselt:

NormalFan and FaceFan accept other kinds of input as well (in particular LatticePolytope),

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 jipilab

  • Branch set to u/jipilab/22498

comment:8 Changed 4 years ago by jipilab

  • Authors set to Jean-Philippe Labbé
  • 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

New commits:

869a623First version
b13f595Added also face fan and reference

comment:9 follow-up: Changed 4 years ago by novoselt

  • 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 full-dimensional polytope for the face fan?

comment:10 in reply to: ↑ 6 Changed 4 years ago by novoselt

Replying to jipilab:

Replying to novoselt:

NormalFan and FaceFan accept other kinds of input as well (in particular LatticePolytope),

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 input-output 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 git

  • Commit changed from b13f5958fbc1b090342583b1bb819cc93507aa70 to 16648a857b2e1366e2cab37c6f30b9d48da58474

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

e6812baRebased on version 7.6.beta6
16648a8Added examples and fixed import

comment:12 in reply to: ↑ 9 Changed 4 years ago by jipilab

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 full-dimensional polytope for the face fan?

Currently it seems to work:

sage: S = Polyhedron(vertices = [[-1, 1/2], [1, -1/2]])
sage: S
A 1-dimensional polyhedron in QQ^2 defined as the convex hull of 2 vertices
sage: FaceFan(S)
Rational polyhedral fan in 2-d lattice M

comment:13 Changed 4 years ago by git

  • Commit changed from 16648a857b2e1366e2cab37c6f30b9d48da58474 to b5c49e6ec798b08ad4a9659791d7d80433919518

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

b5c49e6Corrected doc of face_fan

comment:14 Changed 4 years ago by jipilab

  • Status changed from needs_work to needs_review

comment:15 Changed 4 years ago by novoselt

  • Status changed from needs_review to positive_review

comment:16 Changed 4 years ago by jipilab

Great! Thanks!

comment:17 Changed 4 years ago by vbraun

  • Branch changed from u/jipilab/22498 to b5c49e6ec798b08ad4a9659791d7d80433919518
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.