Implement join of polytopes

jplab commented 6 years ago

From https://www.csun.edu/~ctoth/Handbook/chap15.pdf:

The join of two polytopes P (of dimension d) and Q (of dimension d') is the (d+d'+1)-polytope obtained as the convex hull of P\cup Q after embedding P and Q in a space where their affine hulls are skew.

Depends on #22572

CC: @videlec @mo271 @mkoeppe @fchapoton

Component: geometry

Keywords: days93, polytope, IMA-PolyGeom

Author: Jean-Philippe Labbé

Branch/Commit: 0c9793f

Reviewer: Vincent Delecroix, Moritz Firsching

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

jplab commented 6 years ago

Commit: a14d2c7

jplab commented 6 years ago

Branch: u/jipilab/24848

jplab commented 6 years ago

New commits:

`c807893`	`first version of the join`
`a14d2c7`	`pep8`

jplab commented 6 years ago

Description changed:

--- 
+++ 
@@ -2,3 +2,5 @@

 The join of two polytopes `P` (of dimension d) and `Q` (of dimension d') is the (d+d'+1)-polytope obtained as the convex hull of `P\cup Q` after
 embedding P and Q in a space where their affine hulls are skew.
+
+The usual product is obtained when the intersection of their affine hull is the origin.

jplab commented 6 years ago

Description changed:

--- 
+++ 
@@ -2,5 +2,3 @@

 The join of two polytopes `P` (of dimension d) and `Q` (of dimension d') is the (d+d'+1)-polytope obtained as the convex hull of `P\cup Q` after
 embedding P and Q in a space where their affine hulls are skew.
-
-The usual product is obtained when the intersection of their affine hull is the origin.

videlec commented 6 years ago

Author: Vincent Delecroix

videlec commented 6 years ago

comment:3

According to the developer guide:

the docstring should start with a one line sentence. Then a line break, then a longer description.
better than - ``other`` -- a :class:`Polyhedron_base`., I would just use - ``other`` -- a polyhedron.
there is no need to fill an OUTPUT section as it is already described before.

And I would like to see the definition of a "skew subspace".

This is not the proper thing to do

        try:
            new_ring = self.parent()._coerce_base_ring(other)
        except TypeError:
            raise TypeError("no common canonical parent for objects with parents: " + str(self.parent())
                     + " and " + str(other.parent()))

You should try to coerce the objects to a common parent as in

sage: C = polytopes.cube()
sage: I = polytopes.icosahedron()
sage: cm = get_coercion_model()
sage: cm.common_parent(C, I)
Polyhedra in (Number Field in sqrt5 with defining polynomial x^2 - 5)^3

And even simpler, you could use the decorator @coerce_binop from sage.structure.element.

Moreover, when you construct the resulting polytope you should just use directly the common parent.

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

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

347f99f Made docstring corrections

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

Changed commit from a14d2c7 to 347f99f

jplab commented 6 years ago

comment:5

According to the developer guide:

Yes, you are right. I should read it again every season... I made the changes you suggested.

And I would like to see the definition of a "skew subspace".

I added a short definition.

And even simpler, you could use the decorator @coerce_binop from sage.structure.element.

Unfortunately, doing the join changes the dimension, and hence the parents.

Merci!

jplab commented 6 years ago

comment:6

I'll put you as a review if you don't mind... ;)

jplab commented 6 years ago

Reviewer: Vincent Delecroix

jplab commented 6 years ago

Changed author from Vincent Delecroix to Jean-Philippe Labbé

jplab commented 6 years ago

Dependencies: #22572

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

Changed commit from 347f99f to ec6ad8a

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

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

ec6ad8a Merge branch 'sage8.2.b7' into 24848

mo271 commented 6 years ago

comment:9

This looks like a nice new feature! A few remarks:

In the description: ... of the two polyhedron plus ... --> ... of the two polyhedra plus ...
I would be nice to have some more test, for example:

C = polytopes.hypercube(5)
S = Polyhedron([[1]])
C.join(S).is_combinatorially_isomorphic(C.pyramid())

You wrote the method such that it works also for unbounded polyhedra: this should be doctested for at least one unbounded polyhedron!

Also: see the remarks by Vincent above, they are only partially integrated. You didn't address the coercion question, or am I missing something?

mo271 commented 6 years ago

Changed reviewer from Vincent Delecroix to Vincent Delecroix, Moritz Firsching

jplab commented 6 years ago

comment:10

Replying to @mo271:

This looks like a nice new feature! A few remarks:

In the description: ... of the two polyhedron plus ... --> ... of the two polyhedra plus ...

I would be nice to have some more test, for example:
C = polytopes.hypercube(5)
S = Polyhedron([[1]])
C.join(S).is_combinatorially_isomorphic(C.pyramid())
You wrote the method such that it works also for unbounded polyhedra: this should be doctested for at least one unbounded polyhedron!

Indeed, I added a test and an unbounded example.

Also: see the remarks by Vincent above, they are only partially integrated. You didn't address the coercion question, or am I missing something?

Coercion can not be used since the dimension is included in the parent of Polyhedron objects and they can be different and the output also has a different dimension:

sage: C = polytopes.cube()
sage: S = polytopes.hypercube(2)
sage: C.parent()
Polyhedra in ZZ^3
sage: S.parent()
Polyhedra in ZZ^2
sage: cm = get_coercion_model()
sage: cm.common_parent(C,S)
Traceback (most recent call last):
...
TypeError: no common canonical parent for objects with parents: 'Polyhedra in ZZ^3' and 'Polyhedra in ZZ^2'

That's the explanation of the short sentence I gave above...

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

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

`3b9a7ea`	`Merge branch sage8.2.rc1 with 24848`
`f887745`	`Added tests and examples`

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

Changed commit from ec6ad8a to f887745

jplab commented 6 years ago

comment:13

It still needs to be added to the quick tips of the tutorial.

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

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

`7f5e125`	`fixed typos in polyhedra_quickref.rst`
`bd6c356`	`LateX -> LaTeX in polytope_tikz.rst`
`b1ce45b`	`Several other corrections`
`d526f70`	`renamed tutorial files`
`d7896f8`	`Merge branch 'develop' into 22572`
`597b802`	`Merge branch sage8.2.rc1 into 22572`
`eee533a`	`Corrections from review`
`b74ae85`	`Made tests pass`
`7a8e91b`	`Merge branch thematic tutorial into 24848`
`0c9793f`	`Added join to quickref`

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

Changed commit from f887745 to 0c9793f

jplab commented 6 years ago

Changed keywords from days93, polytope to days93, polytope, IMA-PolyGeom

vbraun commented 6 years ago

Changed branch from u/jipilab/24848 to 0c9793f

sagemath / sage

Implement join of polytopes #24848