Improve the zonotope construction

Reported by: Owned by: gh-kliem major sage-9.3 geometry zonotope jipilab, gh-LaisRast Jean-Philippe Labbé, Jonathan Kliem Jonathan Kliem, Frédéric Chapoton N/A 90a0d60 90a0d6022670062cf14a64c3a64f24235aa6b172

Description

Currently the zonotope just takes the convex hull of the sum of all combinations of the input. With `n` generators it takes therefor the convex hull of `2^n` points.

However, most of those points, will be redundant. Reducing via the Minkowski sum, allows to use this.

Before this ticket:

```sage: from itertools import combinations
sage: cu = polytopes.cube()
sage: sgmt = [p.vector()-q.vector() for p,q in combinations(cu.vertices(),2)]
sage: sgmt2 = set(tuple(x) for x in sgmt)
sage: # %time polytopes.zonotope(sgmt)  # killed due to memory overflow
sage: %time polytopes.zonotope(sgmt2)
CPU times: user 2.06 s, sys: 23.9 ms, total: 2.09 s
Wall time: 2.09 s
A 3-dimensional polyhedron in ZZ^3 defined as the convex hull of 96 vertices
```

With this ticket:

```sage: from itertools import combinations
sage: cu = polytopes.cube()
sage: sgmt = [p.vector()-q.vector() for p,q in combinations(cu.vertices(),2)]
sage: sgmt2 = set(tuple(x) for x in sgmt)
sage: %time polytopes.zonotope(sgmt)
CPU times: user 138 ms, sys: 0 ns, total: 138 ms
Wall time: 138 ms
A 3-dimensional polyhedron in ZZ^3 defined as the convex hull of 96 vertices
sage: %time polytopes.zonotope(sgmt2)
CPU times: user 58 ms, sys: 0 ns, total: 58 ms
Wall time: 57.6 ms
A 3-dimensional polyhedron in ZZ^3 defined as the convex hull of 96 vertices
```

comment:1 Changed 20 months ago by gh-kliem

• Status changed from new to needs_review

comment:2 Changed 20 months ago by jipilab

• Summary changed from Improve the zonotope to Improve the zonotope construction

comment:3 follow-up: ↓ 7 Changed 20 months ago by chapoton

hmm, `reduce` is not very pythonic. Why not use sum ?

comment:4 Changed 20 months ago by git

• Commit changed from a2d1fc5a3e7fa6976fea832b3c90cb3be5c62be7 to 90a0d6022670062cf14a64c3a64f24235aa6b172

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

 ​90a0d60 `use sum`

comment:5 Changed 20 months ago by gh-kliem

Yes, much easier.

comment:6 Changed 20 months ago by chapoton

• Reviewers changed from Jonathan Kliem to Jonathan Kliem, Frédéric Chapoton
• Status changed from needs_review to positive_review

ok, looks good.

comment:7 in reply to: ↑ 3 Changed 20 months ago by jipilab

hmm, `reduce` is not very pythonic. Why not use sum ?
Ah oui? I once discovered it in a python magazine about "tricks" that go unnoticed. Perhaps it is made for more technical things than `+`?