Make outer normal fans readily available

bfacceac-2fda-4b27-b715-a5cf9f114b95 commented 5 years ago

For a polytope P, both NormalFan(P) and P.normal_fan() return the inner normal fan having the inner facet normals as rays. The outer normal fan, using the outer facet normals, is well-known, but not as easy to find in Sage.

As an example, create the polytope on p.193 of Ziegler's "Lectures on Polytopes" with its normal fan:

sage: V=[(-8,-4),(-8,6),(-4,-8),(0,-9),(0,6),(4,-8)]
sage: P=Polyhedron(V)
sage: NormalFan(P)

The result is the inner normal fan of P, which is the outer normal fan of -P.

This ticket adds to Polyhedron.normal_fan an argument direction set to either 'inner' or 'outer' to determine which of the directions to use. The default will stay 'inner' in order to match the default of NormalFan. The description of NormalFan is extended by a hint to use NormalFan(-P) for the outer normal fan.

Additionally, this ticket adds in sage.geometry.polyhedron.representation a method Inequality.outer_normal. This allows to obtain the outer normal vector without having to think about the appropriate sign of Inequality.A() whenever dealing with the facet inequalities of a polyhedron.

CC: @jplab

Component: geometry

Keywords: NormalFan, polytope, days100

Author: Julian Ritter

Branch/Commit: 440689c

Reviewer: Jean-Philippe Labbé, Frédéric Chapoton

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

bfacceac-2fda-4b27-b715-a5cf9f114b95 commented 5 years ago

Branch: u/nailuj/normalfan_outer

bfacceac-2fda-4b27-b715-a5cf9f114b95 commented 5 years ago

New commits:

`57d5508`	`added direction argument to NormalFan`
`484bf56`	`added outer_normal method`

bfacceac-2fda-4b27-b715-a5cf9f114b95 commented 5 years ago

Commit: 484bf56

embray commented 5 years ago

comment:3

Sage 8.8 is to be released fairly soon so unless this is a blocker this should be moved to the next release.

novoselt commented 5 years ago

comment:4

I don't care much about adding direction argument, but I have extremely strong objection to making it the default. There was a reason why inner normals were used for many, many years (like since 2006) - it is consistent with the literature. I understand that some books/articles use the other way, but when neither way is exceptionally uncommon the default choice is pretty much random personal preference when you first create these classes and methods. Once they were created and used for a long time, there is absolutely no reason to change the default whatever it is.

jplab commented 5 years ago

comment:5

Replying to @novoselt:

I don't care much about adding direction argument, but I have extremely strong objection to making it the default. There was a reason why inner normals were used for many, many years (like since 2006) - it is consistent with the literature. I understand that some books/articles use the other way, but when neither way is exceptionally uncommon the default choice is pretty much random personal preference when you first create these classes and methods. Once they were created and used for a long time, there is absolutely no reason to change the default whatever it is.

+1

I would leave the default as it is and add the direction argument to allow to get the variant.

novoselt commented 5 years ago

comment:6

Actually, I think now it would be better to allow quick "direction flip" either on the polytope or the fan, i.e. make them support - operator, instead of making constructors more complicated.

jplab commented 5 years ago

comment:7

Replying to @novoselt:

Actually, I think now it would be better to allow quick "direction flip" either on the polytope or the fan, i.e. make them support - operator, instead of making constructors more complicated.

This seems to already be possible for Polyhedron objects:

sage: p = polytopes.regular_polygon(5)
sage: p.vertices()
(A vertex at (0.5877852522924731?, -0.8090169943749474?),
 A vertex at (0.9510565162951536?, 0.3090169943749474?),
 A vertex at (0, 1),
 A vertex at (-0.5877852522924731?, -0.8090169943749474?),
 A vertex at (-0.9510565162951536?, 0.3090169943749474?))
sage: (-p).vertices()
(A vertex at (-0.5877852522924731?, 0.8090169943749474?),
 A vertex at (-0.9510565162951536?, -0.3090169943749474?),
 A vertex at (0, -1),
 A vertex at (0.587785252292474?, 0.8090169943749474?),
 A vertex at (0.9510565162951536?, -0.3090169943749474?))

Or you have something else in mind?

Yes, I would use NormalFan(-P) or NormalFan(P) depending on whether one wants the inner or outer. This seems like the easiest thing to do. One does not need to go into the Polyhedron constructor...

novoselt commented 5 years ago

comment:8

That's exactly what I meant. I think those who care about directions are likely to read the documentation and discover that these are inner normals. After that, if this is not the desired choice for the user, NormalFan(-P) seems easier and cleaner to use than NormalFan(P, direction="outer").

jplab commented 5 years ago

comment:9

Replying to @novoselt:

That's exactly what I meant. I think those who care about directions are likely to read the documentation and discover that these are inner normals. After that, if this is not the desired choice for the user, NormalFan(-P) seems easier and cleaner to use than NormalFan(P, direction="outer").

I believe that the proposed change would be in the method .normal_fan() of Polyhedron objects, and not at the level of NormalFan, for the reason you mention.

That said, I would change the description of the ticket as follows:

I propose to add to normal_fan an argument direction set to either 'outer' or 'inner' to determine which of the directions to use. The default will stay inner in order to match the default of NormalFan.

Above I would keep the current default.

Additionally, I propose to add in sage.geometry.polyhedron.representation a method Inequality.outer_normal. This allows to obtain the outer normal vector without having to think about the appropriate sign of Inequality.A() whenever dealing with the facet inequalities of a polyhedron.

This is good to me.

Further, I would suggest to add

Use NormalFan(-P) to get the outer normal fan.

in the documentation of NormalFan.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 5 years ago

Changed commit from 484bf56 to b41def5

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 5 years ago

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

`d8763cf`	`Revert "added direction argument to NormalFan"`
`7bfda6e`	`added hint to NormalFan(-P)`
`0c653c9`	`added direction argument to Polyhedron.normal_fan`
`b41def5`	`Merge branch 'develop' into normalfan_outer`

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 5 years ago

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

fd3e899 Fixed typo

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 5 years ago

Changed commit from b41def5 to fd3e899

bfacceac-2fda-4b27-b715-a5cf9f114b95 commented 5 years ago

comment:12

Replying to @jplab:

Replying to @novoselt:

That's exactly what I meant. I think those who care about directions are likely to read the documentation and discover that these are inner normals. After that, if this is not the desired choice for the user, NormalFan(-P) seems easier and cleaner to use than NormalFan(P, direction="outer").

I believe that the proposed change would be in the method .normal_fan() of Polyhedron objects, and not at the level of NormalFan, for the reason you mention.

Yes. I stumbled upon this inner-outer issue through Polyhedron.normal_fan(). This is why I added jipilab in CC in the first place, and this is where I should have proposed to make 'outer' the default – my bad. I'm fine with 'inner' as default in both files. My main goal was easier access to outer normal fans, which is now available and explained in the docstrings.

That said, I would change the description of the ticket as follows:

I propose to add to normal_fan an argument direction set to either 'outer' or 'inner' to determine which of the directions to use. The default will stay inner in order to match the default of NormalFan.

Done.

Further, I would suggest to add

Use NormalFan(-P) to get the outer normal fan.

in the documentation of NormalFan.

Done.

bfacceac-2fda-4b27-b715-a5cf9f114b95 commented 5 years ago

Description changed:

--- 
+++ 
@@ -19,8 +19,9 @@
 In both cases, the normal vectors obtained are directed towards the interior of the polytope. 
 Therefore, the resulting fan differs from what would be obtained when using the outer normal vectors instead.

-I propose to add to `NormalFan` an argument `direction` set to either `'outer'` or `'inner'` to determine which of the directions to use. 
-In line with the definition in Ziegler's book, I would prefer to make `'outer'` the default choice.
+
+I propose to add to `Polyhedron.normal_fan` an argument `direction` set to either `'inner'` or `'outer'` to determine which of the directions to use. The default will stay `'inner'` in order to match the default of `NormalFan`.
+

 Additionally, I propose to add in `sage.geometry.polyhedron.representation` a method `Inequality.outer_normal`.
 This allows to obtain the outer normal vector without having to think about the appropriate sign of `Inequality.A()` whenever dealing with the facet inequalities of a polyhedron.

jplab commented 5 years ago

Reviewer: Jean-Philippe Labbé

jplab commented 5 years ago

Changed keywords from NormalFan, polytope to NormalFan, polytope, days100

jplab commented 5 years ago

comment:13

The optional parameters should receive an appropriate doctest. For example:

sage: p = polytopes.regular_polygon(4,base_ring=QQ).pyramid()
sage: inner_nf = p.normal_fan()
sage: inner_nf.rays()
N( 1,  0,  0),
N(-1,  1,  1),
N(-1,  1, -1),
N(-1, -1, -1),
N(-1, -1,  1)
in 3-d lattice N

sage: outer_nf = p.normal_fan(direction='outer')
sage: outer_nf.rays()
N(-1,  0,  0),
N( 1,  1, -1),
N( 1,  1,  1),
N( 1, -1,  1),
N( 1, -1, -1)
in 3-d lattice N

Further, it would be nice to disallow such things:

sage: outer_nf = p.normal_fan(direction='blabla')

by checking that direction is one of the two allowed things (see the volume function for a similar handling).

Remove the space before the semi-colon in the docstring of normal_fan.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 5 years ago

Changed commit from fd3e899 to 308dada

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 5 years ago

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

`257d367`	`Added check that the direction is inner or outer`
`5ae5e68`	`pyflakes fix`
`691046a`	`fixed typo`
`308dada`	`added examples`

bfacceac-2fda-4b27-b715-a5cf9f114b95 commented 5 years ago

comment:15

Replying to @jplab:

The optional parameters should receive an appropriate doctest. For example:

   sage: p = polytopes.regular_polygon(4,base_ring=QQ).pyramid()
   sage: inner_nf = p.normal_fan()
   sage: inner_nf.rays()
   N( 1,  0,  0),
   N(-1,  1,  1),
   N(-1,  1, -1),
   N(-1, -1, -1),
   N(-1, -1,  1)
   in 3-d lattice N

   sage: outer_nf = p.normal_fan(direction='outer')
   sage: outer_nf.rays()
   N(-1,  0,  0),
   N( 1,  1, -1),
   N( 1,  1,  1),
   N( 1, -1,  1),
   N( 1, -1, -1)
   in 3-d lattice N

I added a 2-d example testing inner, outer, and an invalid direction.

Further, it would be nice to disallow such things:
sage: outer_nf = p.normal_fan(direction='blabla')
by checking that direction is one of the two allowed things (see the volume function for a similar handling).

Done.

Remove the space before the semi-colon in the docstring of normal_fan.

Done.

jplab commented 5 years ago

comment:16

Great!

Could you do one change: the backtick in the error message should be a single quote.

I would also fix the title of the ticket and the description to reflect the actual changes involved.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 5 years ago

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

9d20a1d replaced backtick by single quote

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 5 years ago

Changed commit from 308dada to 9d20a1d

bfacceac-2fda-4b27-b715-a5cf9f114b95 commented 5 years ago

comment:18

Replying to @jplab:

Could you do one change: the backtick in the error message should be a single quote.

Done.

I would also fix the title of the ticket and the description to reflect the actual changes involved.

Done.

bfacceac-2fda-4b27-b715-a5cf9f114b95 commented 5 years ago

Description changed:

--- 
+++ 
@@ -1,28 +1,17 @@
-
+For a polytope `P`, both `NormalFan(P)` and `P.normal_fan()` return the inner normal fan having the inner facet normals as rays. The outer normal fan, using the outer facet normals, is well-known, but not as easy to find in Sage.

 As an example, create the polytope on p.193 of Ziegler's "Lectures on Polytopes" with its normal fan:

sage: V=[(-8,-4),(-8,6),(-4,-8),(0,-9),(0,6),(4,-8)] sage: P=Polyhedron(V) -sage: L=LatticePolytope(V) -sage: FanP, FanL = NormalFan(P), NormalFan(L) -sage: FanP == FanL -True +sage: NormalFan(P)


-The two fans are equal, but they are not the same as the one presented in Ziegler's book.
-In fact, following to the definition there, `FanP` and `FanL` give the normal fan of `-P`.
+The result is the inner normal fan of `P`, which is the outer normal fan of `-P`.

-The construction of `NormalFan(polytope)` uses the normal vectors of the facets, given by `polytope.facet_normals()` for a `LatticePolytope` 
-or given by `ieq.A() for ieq in polytope.inequalities()` for a `Polyhedron`.
-In both cases, the normal vectors obtained are directed towards the interior of the polytope. 
-Therefore, the resulting fan differs from what would be obtained when using the outer normal vectors instead.
+This ticket adds to `Polyhedron.normal_fan` an argument `direction` set to either `'inner'` or `'outer'` to determine which of the directions to use. The default will stay `'inner'` in order to match the default of `NormalFan`. The description of `NormalFan` is extended by a hint to use `NormalFan(-P)` for the outer normal fan.

-
-I propose to add to `Polyhedron.normal_fan` an argument `direction` set to either `'inner'` or `'outer'` to determine which of the directions to use. The default will stay `'inner'` in order to match the default of `NormalFan`.
-
-
-Additionally, I propose to add in `sage.geometry.polyhedron.representation` a method `Inequality.outer_normal`.
+Additionally, this ticket adds in `sage.geometry.polyhedron.representation` a method `Inequality.outer_normal`.
 This allows to obtain the outer normal vector without having to think about the appropriate sign of `Inequality.A()` whenever dealing with the facet inequalities of a polyhedron.

jplab commented 5 years ago

comment:19

The doctest still has backticks.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 5 years ago

Changed commit from 9d20a1d to 440689c

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 5 years ago

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

440689c replaced backticks in doctest