Opened 5 years ago

Closed 5 years ago

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

Reported by: Owned by: jipilab major sage-7.6 geometry geometry, days84, polytope, fan moritz, mkoeppe, vdelecroix, tmonteil, chapoton Jean-Philippe Labbé Andrey Novoseltsev N/A examples b5c49e6 b5c49e6ec798b08ad4a9659791d7d80433919518

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.

### comment:1 follow-up: ↓ 2 Changed 5 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 5 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: ↓ 4 Changed 5 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 5 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: ↓ 6 Changed 5 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: ↓ 10 Changed 5 years ago by jipilab

`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 5 years ago by jipilab

• Branch set to u/jipilab/22498

### comment:8 Changed 5 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:

 ​869a623 `First version` ​b13f595 `Added also face fan and reference`

### comment:9 follow-up: ↓ 12 Changed 5 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 5 years ago by 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 5 years ago by git

• Commit changed from b13f5958fbc1b090342583b1bb819cc93507aa70 to 16648a857b2e1366e2cab37c6f30b9d48da58474

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

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

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

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 5 years ago by git

• 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 5 years ago by jipilab

• Status changed from needs_work to needs_review

### comment:15 Changed 5 years ago by novoselt

• Status changed from needs_review to positive_review

Great! Thanks!

### comment:17 Changed 5 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.