Opened 2 years ago

Closed 23 months ago

#24848 closed enhancement (fixed)

Implement join of polytopes

Reported by: jipilab Owned by:
Priority: major Milestone: sage-8.3
Component: geometry Keywords: days93, polytope, IMA-PolyGeom
Cc: vdelecroix, moritz, mkoeppe, chapoton Merged in:
Authors: Jean-Philippe Labbé Reviewers: Vincent Delecroix, Moritz Firsching
Report Upstream: N/A Work issues:
Branch: 0c9793f (Commits) Commit: 0c9793fcefc2749afd0ff4b3b2b60f50aaf93805
Dependencies: #22572 Stopgaps:

Description (last modified by jipilab)

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.

Change History (18)

comment:1 Changed 2 years ago by jipilab

  • Branch set to u/jipilab/24848
  • Commit set to a14d2c7fcdc26ad61062c1d715d5f338836ecdfb
  • Description modified (diff)
  • Status changed from new to needs_review

New commits:

c807893first version of the join
a14d2c7pep8

comment:2 Changed 2 years ago by jipilab

  • Description modified (diff)

comment:3 follow-up: Changed 2 years ago by vdelecroix

  • Authors set to Vincent Delecroix
  • Status changed from needs_review to needs_work

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.

comment:4 Changed 2 years ago by git

  • Commit changed from a14d2c7fcdc26ad61062c1d715d5f338836ecdfb to 347f99f7b1204076f6359ac89bc88b8f4a389106

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

347f99fMade docstring corrections

comment:5 in reply to: ↑ 3 Changed 2 years ago by jipilab

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!

comment:6 Changed 2 years ago by jipilab

  • Authors changed from Vincent Delecroix to Jean-Philippe Labbé
  • Reviewers set to Vincent Delecroix
  • Status changed from needs_work to needs_review

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

comment:7 Changed 2 years ago by jipilab

  • Dependencies set to #22572

comment:8 Changed 2 years ago by git

  • Commit changed from 347f99f7b1204076f6359ac89bc88b8f4a389106 to ec6ad8a89ed5094a187215e93b895662ef80a1dd

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

ec6ad8aMerge branch 'sage8.2.b7' into 24848

comment:9 follow-up: Changed 2 years ago by moritz

  • Reviewers changed from Vincent Delecroix to Vincent Delecroix, Moritz Firsching
  • Status changed from needs_review to needs_work

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?

comment:10 in reply to: ↑ 9 Changed 2 years ago by jipilab

Replying to moritz:

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

comment:11 Changed 2 years ago by git

  • Commit changed from ec6ad8a89ed5094a187215e93b895662ef80a1dd to f8877456006eeee0dbb428e1cfc6ec707e4b1153

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

3b9a7eaMerge branch sage8.2.rc1 with 24848
f887745Added tests and examples

comment:12 Changed 2 years ago by jipilab

  • Status changed from needs_work to needs_review

comment:13 Changed 2 years ago by jipilab

  • Status changed from needs_review to needs_work

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

comment:14 Changed 2 years ago by git

  • Commit changed from f8877456006eeee0dbb428e1cfc6ec707e4b1153 to 0c9793fcefc2749afd0ff4b3b2b60f50aaf93805

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

7f5e125fixed typos in polyhedra_quickref.rst
bd6c356LateX -> LaTeX in polytope_tikz.rst
b1ce45bSeveral other corrections
d526f70renamed tutorial files
d7896f8Merge branch 'develop' into 22572
597b802Merge branch sage8.2.rc1 into 22572
eee533aCorrections from review
b74ae85Made tests pass
7a8e91bMerge branch thematic tutorial into 24848
0c9793fAdded join to quickref

comment:15 Changed 2 years ago by jipilab

  • Keywords IMA-PolyGeom added
  • Status changed from needs_work to needs_review

comment:16 Changed 2 years ago by moritz

  • Status changed from needs_review to positive_review

comment:17 Changed 2 years ago by jipilab

  • Milestone changed from sage-8.2 to sage-8.3

comment:18 Changed 23 months ago by vbraun

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