id summary reporter owner description type status priority milestone component resolution keywords cc merged author reviewer upstream work_issues branch commit dependencies stopgaps
31038 Improve the zonotope construction gh-kliem "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
}}}" enhancement closed major sage-9.3 geometry fixed zonotope jipilab gh-LaisRast Jean-Philippe Labbé, Jonathan Kliem Jonathan Kliem, Frédéric Chapoton N/A 90a0d6022670062cf14a64c3a64f24235aa6b172 90a0d6022670062cf14a64c3a64f24235aa6b172