Add .normal_fan() and .face_fan() methods for rational bounded polyhedra

[jplab]

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.

CC: @mo271 @mkoeppe @videlec @sagetrac-tmonteil @fchapoton

Component: geometry

Keywords: days84, polytope, fan

Work Issues: examples

Author: Jean-Philippe Labbé

Branch/Commit: b5c49e6

Reviewer: Andrey Novoseltsev

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

[novoselt]

comment:1

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

[jplab]

comment:2

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?

[novoselt]

comment:3

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).

[jplab]

comment:4

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.

[novoselt]

comment:5

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 ;-)

[jplab]

comment:6

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?

[jplab]

Branch: u/jipilab/22498

[jplab]

New commits:

869a623	First version
b13f595	Added also face fan and reference

[jplab]

Author: Jean-Philippe Labbé

[jplab]

Commit: b13f595

[novoselt]

Work Issues: examples

[novoselt]

comment:9

There are no examples!!!

Also, is it really necessary to have full-dimensional polytope for the face fan?

[novoselt]

Reviewer: Andrey Novoseltsev

[novoselt]

comment:10

Replying to @jplab:

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 ;-)

[sagetrac-git]

Changed commit from b13f595 to 16648a8

[sagetrac-git]

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

e6812ba	Rebased on version 7.6.beta6
16648a8	Added examples and fixed import

[jplab]

comment:12

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

[sagetrac-git]

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

b5c49e6

Corrected doc of face_fan

[sagetrac-git]

Changed commit from 16648a8 to b5c49e6

[jplab]

comment:16

Great! Thanks!

[vbraun]

Changed branch from u/jipilab/22498 to b5c49e6