# Polyhedron partition and Induction¶

Polyhedron partition, polyhedron exchange transformations and induced transformations

EXAMPLES:

A polyhedron partition:

sage: from slabbe import PolyhedronPartition
sage: h = 1/3
sage: p = Polyhedron([(0,h),(0,1),(h,1)])
sage: q = Polyhedron([(0,0), (0,h), (h,1), (h,0)])
sage: r = Polyhedron([(h,1), (1,1), (1,h), (h,0)])
sage: s = Polyhedron([(h,0), (1,0), (1,h)])
sage: P = PolyhedronPartition({0:p, 1:q, 2:r, 3:s})
sage: P.is_pairwise_disjoint()
True
sage: list(P)
[(0, A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 3 vertices),
(1, A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 4 vertices),
(2, A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 4 vertices),
(3, A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 3 vertices)]
sage: G = P.plot()


Applying a rationnal rotation:

sage: from slabbe import PolyhedronExchangeTransformation as PET
sage: base = identity_matrix(2)
sage: translation = vector((2/3, 0))
sage: u = PET.toral_translation(base, translation)
sage: Q = u(P)
sage: Q
Polyhedron partition of 4 atoms with 4 letters


Inducing an irrationnal rotation on a subdomain:

sage: z = polygen(QQ, 'z') #z = QQ['z'].0 # same as
sage: K = NumberField(z**2-z-1, 'phi', embedding=RR(1.6))
sage: phi = K.gen()
sage: h = 1/phi^2
sage: p = Polyhedron([(0,h),(0,1),(h,1)])
sage: q = Polyhedron([(0,0), (0,h), (h,1), (h,0)])
sage: r = Polyhedron([(h,1), (1,1), (1,h), (h,0)])
sage: s = Polyhedron([(h,0), (1,0), (1,h)])
sage: P = PolyhedronPartition({0:p, 1:q, 2:r, 3:s}, base_ring=K)
sage: base = identity_matrix(2)
sage: translation = vector((1/phi, 0))
sage: u = PET.toral_translation(base, translation)
sage: ieq = [h, -1, 0]   # x0 <= h
sage: P1,sub01 = u.induced_partition(ieq, P)
sage: P1
Polyhedron partition of 7 atoms with 7 letters
sage: sub01
{0: [0, 2],
1: [1, 2],
2: [1, 3],
3: [0, 2, 2],
4: [1, 2, 2],
5: [1, 3, 2],
6: [1, 3, 3]}


AUTHORS:

• Sébastien Labbé, November 2017, initial version of polyhedron partitions
• Sébastien Labbé, January 2019, added a class for polyhedron exchange transformations
class slabbe.polyhedron_partition.PolyhedronExchangeTransformation(partition, translations)

Bases: object

Polyhedron Exchange Transformation (PET).

INPUT:

• partition – a polyhedron partition
• translations – list or dict

EXAMPLES:

sage: from slabbe import PolyhedronPartition, PolyhedronExchangeTransformation
sage: h = 1/3
sage: p = Polyhedron([(0,0),(h,0),(h,1),(0,1)])
sage: q = Polyhedron([(1,0),(h,0),(h,1),(1,1)])
sage: P = PolyhedronPartition({0:p, 1:q})
sage: T = {0:(1-h,0), 1:(-h,0)}
sage: PolyhedronExchangeTransformation(P, T)
Polyhedron Exchange Transformation of
Polyhedron partition of 2 atoms with 2 letters
with translations {0: (2/3, 0), 1: (-1/3, 0)}


REFERENCES:

• Schwartz, Richard Evan. The Octagonal PETs. First Edition edition. Providence, Rhode Island: American Mathematical Society, 2014.
ambient_space()

EXAMPLES:

sage: from slabbe import PolyhedronPartition, PolyhedronExchangeTransformation
sage: h = 1/3
sage: p = Polyhedron([(0,0),(h,0),(h,1),(0,1)])
sage: q = Polyhedron([(1,0),(h,0),(h,1),(1,1)])
sage: P = PolyhedronPartition({0:p, 1:q})
sage: T = {0:(1-h,0), 1:(-h,0)}
sage: F = PolyhedronExchangeTransformation(P, T)
sage: F.ambient_space()
Vector space of dimension 2 over Rational Field

cylinder(word, partition=None, key_fn=None)

Return the region associated to the coding word.

INPUT:

• word – list
• partition – polyhedron partition (default:None), if None, it uses the domain partition of the transformation
• key_fn – function (default:lambda a,b:(a,b)), the concatenation function

OUTPUT:

polyhedron partition

EXAMPLES:

sage: from slabbe import PolyhedronPartition
sage: h = 1/2
sage: p = Polyhedron([(0,h),(0,1),(h,1)])
sage: q = Polyhedron([(0,0), (0,h), (h,1), (1,1), (1,h), (h,0)])
sage: r = Polyhedron([(h,0), (1,0), (1,h)])
sage: P = PolyhedronPartition([p,q,r])

sage: from slabbe import PolyhedronExchangeTransformation as PET
sage: base = identity_matrix(2)
sage: translation = vector((1/3, 0))
sage: u = PET.toral_translation(base, translation)
sage: c = u.cylinder([2,2], P); c
Polyhedron partition of 1 atoms with 1 letters
sage: c.alphabet()
{(2, 2)}

sage: u.cylinder([1,1], P)
Polyhedron partition of 2 atoms with 1 letters
sage: u.cylinder([1], P)
Polyhedron partition of 1 atoms with 1 letters


Cylinders of words of length 0:

sage: u.cylinder([], P).volume()
1


Cylinders of words of length 1:

sage: C1 = [u.cylinder([a], P).volume() for a in range(3)]
sage: C1
[1/8, 3/4, 1/8]
sage: sum(C1)
1


Cylinders of words of length 2:

sage: import itertools
sage: L2 = itertools.product(range(3),repeat=2)
sage: C2 = [u.cylinder([a,b], P).volume() for (a,b) in L2]
sage: C2
[1/72, 1/9, 0, 1/9, 19/36, 1/9, 0, 1/9, 1/72]
sage: sum(C2)
1


Cylinders of words of length 3:

sage: L3 = itertools.product(range(3),repeat=3)
sage: C3 = [u.cylinder([a,b,c], P).volume() for (a,b,c) in L3]
sage: sum(C3)
1


TESTS:

sage: u.cylinder([0,0,0], P)
Polyhedron partition of 0 atoms with 0 letters
sage: u.cylinder([2,3], P)
Polyhedron partition of 0 atoms with 0 letters
sage: u.cylinder([2,1], P)
Polyhedron partition of 1 atoms with 1 letters
sage: u.cylinder([], P)
Polyhedron partition of 3 atoms with 3 letters

cylinders(size, partition=None, key_fn=None)

Return the cylinders of given size.

INPUT:

• size – nonnegative integer
• partition – polyhedron partition (default:None), if None, it uses the domain partition of the transformation
• key_fn – function (default:lambda a,b:a+b and every key of atoms of the partition is changed into a singleton tuple), the concatenation function

OUTPUT:

polyhedron partition

EXAMPLES:

sage: from slabbe import PolyhedronExchangeTransformation as PET
sage: base = identity_matrix(2)
sage: translation = vector((1/3, 0))
sage: u = PET.toral_translation(base, translation)
sage: [u.cylinders(i) for i in range(5)]
[Polyhedron partition of 1 atoms with 1 letters,
Polyhedron partition of 2 atoms with 2 letters,
Polyhedron partition of 3 atoms with 3 letters,
Polyhedron partition of 3 atoms with 3 letters,
Polyhedron partition of 3 atoms with 3 letters]
sage: [u.cylinders(i).alphabet() for i in range(5)]
[{()},
{(0,), (1,)},
{(0, 0), (0, 1), (1, 0)},
{(0, 0, 1), (0, 1, 0), (1, 0, 0)},
{(0, 0, 1, 0), (0, 1, 0, 0), (1, 0, 0, 1)}]

domain()

Return the domain of the exchange transformation.

OUTPUT:

a polyhedron

EXAMPLES:

sage: from slabbe import PolyhedronPartition, PolyhedronExchangeTransformation
sage: h = 1/3
sage: p = Polyhedron([(0,0),(h,0),(h,1),(0,1)])
sage: q = Polyhedron([(1,0),(h,0),(h,1),(1,1)])
sage: P = PolyhedronPartition({0:p, 1:q})
sage: T = {0:(1-h,0), 1:(-h,0)}
sage: F = PolyhedronExchangeTransformation(P, T)
sage: F.domain()
A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 4 vertices
sage: F.domain().vertices()
(A vertex at (0, 0),
A vertex at (0, 1),
A vertex at (1, 0),
A vertex at (1, 1))

image_partition()

Return the partition of the image.

EXAMPLES:

sage: from slabbe import PolyhedronPartition, PolyhedronExchangeTransformation
sage: h = 1/3
sage: p = Polyhedron([(0,0),(h,0),(h,1),(0,1)])
sage: q = Polyhedron([(1,0),(h,0),(h,1),(1,1)])
sage: P = PolyhedronPartition({0:p, 1:q})
sage: T = {0:(1-h,0), 1:(-h,0)}
sage: F = PolyhedronExchangeTransformation(P, T)
sage: F.image_partition()
Polyhedron partition of 2 atoms with 2 letters

induced_in_partition(ieq, partition=None)

Returns the partition of the induced transformation on the domain. given by an inequality.

INPUT:

• ieq – list, an inequality. An entry equal to “[-1,7,3,4]” represents the inequality 7x_1+3x_2+4x_3>= 1.
• partition – polyhedron partition (default:None), if None, it uses the domain partition of the transformation

OUTPUT:

dict of polyhedron partitions with keys giving the return time

EXAMPLES:

sage: from slabbe import PolyhedronPartition
sage: h = 1/3
sage: p = Polyhedron([(0,h),(0,1),(h,1)])
sage: q = Polyhedron([(0,0), (0,h), (h,1), (h,0)])
sage: r = Polyhedron([(h,1), (1,1), (1,h), (h,0)])
sage: s = Polyhedron([(h,0), (1,0), (1,h)])
sage: P = PolyhedronPartition({0:p, 1:q, 2:r, 3:s})

sage: from slabbe import PolyhedronExchangeTransformation as PET
sage: base = identity_matrix(2)
sage: translation = vector((1/3, 0))
sage: u = PET.toral_translation(base, translation)
sage: ieq = [h, -1, 0]   # x0 <= h
sage: u.induced_in_partition(ieq, P)
{3: Polyhedron partition of 4 atoms with 4 letters}

sage: P = PolyhedronPartition({0:p, 1:q, 2:r, 3:s})
sage: ieq2 = [1/2, -1, 0]   # x0 <= 1/2
sage: d = u.induced_in_partition(ieq2, P)
sage: d
{1: Polyhedron partition of 2 atoms with 2 letters,
2: Polyhedron partition of 3 atoms with 3 letters,
3: Polyhedron partition of 4 atoms with 4 letters}

induced_out_partition(ieq, partition=None)

Returns the output partition obtained as the induction of the transformation on the domain given by an inequality.

Note: the output partition corresponds to the arrival partition in the domain, not the initial one.

INPUT:

• ieq – list, an inequality. An entry equal to “[-1,7,3,4]” represents the inequality 7x_1+3x_2+4x_3>= 1.
• partition – polyhedron partition (default:None), if None, it uses the domain partition of the transformation

OUTPUT:

dict of polyhedron partitions with keys giving the return time

EXAMPLES:

sage: from slabbe import PolyhedronExchangeTransformation as PET
sage: base = identity_matrix(2)
sage: translation = vector((1/3, 0))
sage: u = PET.toral_translation(base, translation)
sage: ieq = [1/2, -1, 0]   # x0 <= 1/2
sage: d = u.induced_out_partition(ieq)
sage: [(i, d[i], d[i].alphabet()) for i in d]
[(1, Polyhedron partition of 1 atoms with 1 letters, {(0,)}),
(2, Polyhedron partition of 1 atoms with 1 letters, {(0, 1)}),
(3, Polyhedron partition of 1 atoms with 1 letters, {(0, 0, 1)})]

sage: from slabbe import PolyhedronPartition
sage: h = 1/3
sage: p = Polyhedron([(0,h),(0,1),(h,1)])
sage: q = Polyhedron([(0,0), (0,h), (h,1), (h,0)])
sage: r = Polyhedron([(h,1), (1,1), (1,h), (h,0)])
sage: s = Polyhedron([(h,0), (1,0), (1,h)])
sage: P = PolyhedronPartition({0:p, 1:q, 2:r, 3:s})
sage: ieq = [h, -1, 0]   # x0 <= h
sage: d = u.induced_out_partition(ieq, P)
sage: [(i, d[i], d[i].alphabet()) for i in d]
[(3,
Polyhedron partition of 4 atoms with 4 letters,
{(0, 2, 2), (1, 2, 2), (1, 2, 3), (1, 3, 3)})]

sage: ieq2 = [1/2, -1, 0]   # x0 <= 1/2
sage: d = u.induced_out_partition(ieq2, P)
sage: [(i, d[i], d[i].alphabet()) for i in d]
[(1, Polyhedron partition of 2 atoms with 2 letters, {(0,), (1,)}),
(2, Polyhedron partition of 3 atoms with 3 letters, {(2, 2), (2, 3), (3, 3)}),
(3,
Polyhedron partition of 4 atoms with 4 letters,
{(0, 2, 2), (1, 2, 2), (1, 2, 3), (1, 3, 3)})]
sage: Q = PolyhedronPartition(d[1].atoms()+d[2].atoms()+d[3].atoms())
sage: Q.is_pairwise_disjoint()
True

sage: P = PolyhedronPartition({0:p, 1:q, 2:r, 3:s})
sage: ieq3 = [-1/2, 1, 0]   # x0 >= 1/2
sage: u.induced_out_partition(ieq3, P)
{1: Polyhedron partition of 2 atoms with 2 letters,
2: Polyhedron partition of 3 atoms with 3 letters,
3: Polyhedron partition of 4 atoms with 4 letters}


It is an error if the induced region is empty:

sage: P = PolyhedronPartition({0:p, 1:q, 2:r, 3:s})
sage: ieq4 = [-1/2, -1, 0]   # x0 <= -1/2
sage: u.induced_out_partition(ieq4, P)
Traceback (most recent call last):
...
ValueError: Inequality An inequality (-2, 0) x - 1 >= 0 does
not intersect P (=Polyhedron partition of 4 atoms with 4
letters)


The whole domain:

sage: P = PolyhedronPartition({0:p, 1:q, 2:r, 3:s})
sage: ieq5 = [1/2, 1, 0]   # x0 >= -1/2
sage: d = u.induced_out_partition(ieq5, P)
sage: [(i, d[i], d[i].alphabet()) for i in d]
[(1,
Polyhedron partition of 6 atoms with 4 letters,
{(0,), (1,), (2,), (3,)})]


An irrational rotation:

sage: z = polygen(QQ, 'z') #z = QQ['z'].0 # same as
sage: K = NumberField(z**2-z-1, 'phi', embedding=RR(1.6))
sage: phi = K.gen()
sage: h = 1/phi^2
sage: p = Polyhedron([(0,h),(0,1),(h,1)])
sage: q = Polyhedron([(0,0), (0,h), (h,1), (h,0)])
sage: r = Polyhedron([(h,1), (1,1), (1,h), (h,0)])
sage: s = Polyhedron([(h,0), (1,0), (1,h)])
sage: P = PolyhedronPartition({0:p, 1:q, 2:r, 3:s}, base_ring=K)
sage: base = identity_matrix(2)
sage: translation = vector((1/phi, 0))
sage: u = PET.toral_translation(base, translation)
sage: ieq = [phi^-4, -1, 0]   # x0 <= phi^-4
sage: d = u.induced_out_partition(ieq, P)
sage: d
{5: Polyhedron partition of 6 atoms with 6 letters,
8: Polyhedron partition of 9 atoms with 9 letters}

induced_partition(ieq, partition=None, substitution_type='dict')

Returns the partition of the induced transformation on the domain.

INPUT:

• ieq – list, an inequality. An entry equal to “[-1,7,3,4]” represents the inequality 7x_1+3x_2+4x_3>= 1.
• partition – polyhedron partition (default:None), if None, it uses the domain partition of the transformation
• substitution_type – string (default:'dict'), if 'column' or 'row', it returns a substitution2d, otherwise it returns a dict.

OUTPUT:

• a polyhedron partition
• a substitution2d or a dict

EXAMPLES:

sage: from slabbe import PolyhedronExchangeTransformation as PET
sage: base = identity_matrix(2)
sage: translation = vector((1/3, 0))
sage: u = PET.toral_translation(base, translation)


We compute the induced partition of a polyhedron exchange transformation on a subdomain given by an inequality:

sage: ieq = [1/3, -1, 0]   # x0 <= 1/3
sage: u.induced_partition(ieq)
(Polyhedron partition of 1 atoms with 1 letters,
{0: [0, 0, 1]})
sage: ieq = [1/2, -1, 0]   # x0 <= 1/2
sage: u.induced_partition(ieq)
(Polyhedron partition of 3 atoms with 3 letters,
{0: [0], 1: [0, 1], 2: [0, 0, 1]})


The second output can be turned into a column or a row Substitution2d if desired:

sage: u.induced_partition(ieq, substitution_type='row')
(Polyhedron partition of 3 atoms with 3 letters,
Substitution 2d: {0: [[0]], 1: [[0], [1]], 2: [[0], [0], [1]]})


Now we construct a another coding partition:

sage: from slabbe import PolyhedronPartition
sage: h = 1/3
sage: p = Polyhedron([(0,h),(0,1),(h,1)])
sage: q = Polyhedron([(0,0), (0,h), (h,1), (h,0)])
sage: r = Polyhedron([(h,1), (1,1), (1,h), (h,0)])
sage: s = Polyhedron([(h,0), (1,0), (1,h)])
sage: P = PolyhedronPartition({0:p, 1:q, 2:r, 3:s})


We use this other partition to compute the induced partition:

sage: ieq = [h, -1, 0]   # x0 <= h
sage: Q,sub = u.induced_partition(ieq, P)
sage: Q
Polyhedron partition of 4 atoms with 4 letters
sage: sub
{0: [0, 2, 2], 1: [1, 2, 2], 2: [1, 2, 3], 3: [1, 3, 3]}

sage: P = PolyhedronPartition({0:p, 1:q, 2:r, 3:s})
sage: ieq2 = [1/2, -1, 0]   # x0 <= 1/2
sage: Q,sub = u.induced_partition(ieq2, P)
sage: Q
Polyhedron partition of 9 atoms with 9 letters
sage: sub
{0: [0],
1: [1],
2: [2, 2],
3: [2, 3],
4: [3, 3],
5: [0, 2, 2],
6: [1, 2, 2],
7: [1, 2, 3],
8: [1, 3, 3]}


Irrationnal rotations:

sage: z = polygen(QQ, 'z') #z = QQ['z'].0 # same as
sage: K = NumberField(z**2-z-1, 'phi', embedding=RR(1.6))
sage: phi = K.gen()
sage: h = 1/phi^2
sage: p = Polyhedron([(0,h),(0,1),(h,1)])
sage: q = Polyhedron([(0,0), (0,h), (h,1), (h,0)])
sage: r = Polyhedron([(h,1), (1,1), (1,h), (h,0)])
sage: s = Polyhedron([(h,0), (1,0), (1,h)])
sage: P = PolyhedronPartition({0:p, 1:q, 2:r, 3:s}, base_ring=K)
sage: base = identity_matrix(2)
sage: translation = vector((1/phi, 0))
sage: u = PET.toral_translation(base, translation)
sage: ieq = [h, -1, 0]   # x0 <= h
sage: P1,sub01 = u.induced_partition(ieq, P)
sage: P1
Polyhedron partition of 7 atoms with 7 letters
sage: sub01
{0: [0, 2],
1: [1, 2],
2: [1, 3],
3: [0, 2, 2],
4: [1, 2, 2],
5: [1, 3, 2],
6: [1, 3, 3]}


We do the induction on a smaller domain:

sage: ieq2 = [1/phi^3, -1, 0]   # x0 <= h
sage: P2,sub02 = u.induced_partition(ieq2, P)
sage: P2
Polyhedron partition of 10 atoms with 10 letters
sage: sub02
{0: [0, 2, 2],
1: [1, 2, 2],
2: [1, 3, 2],
3: [1, 3, 3],
4: [0, 2, 0, 2, 2],
5: [0, 2, 1, 2, 2],
6: [1, 2, 1, 2, 2],
7: [1, 2, 1, 3, 2],
8: [1, 3, 1, 3, 2],
9: [1, 3, 1, 3, 3]}


We check that inductions commute:

sage: base = diagonal_matrix((phi^-2,1))
sage: translation = vector((phi^-3, 0))
sage: u1 = PET.toral_translation(base, translation)
sage: P2_alt,sub12 = u1.induced_partition(ieq2, P1)
sage: P2_alt
Polyhedron partition of 10 atoms with 10 letters
sage: P2_alt == P2
True


Up to a permutation of the alphabet, sub02 and sub01*sub12 are equal:

sage: s01 = WordMorphism(sub01)
sage: s12 = WordMorphism(sub12)
sage: s02 = WordMorphism(sub02)
sage: s02
WordMorphism: 0->022, 1->122, 2->132, 3->133, 4->02022, 5->02122, 6->12122, 7->12132, 8->13132, 9->13133
sage: s01*s12 == s02
True


By chance, the above is true, but in general, we have:

sage: perm = WordMorphism(P2.keys_permutation(P2_alt))
sage: perm
WordMorphism: 0->0, 1->1, 2->2, 3->3, 4->4, 5->5, 6->6, 7->7, 8->8, 9->9
sage: s01*s12*perm == s02
True

induced_transformation(ieq)

Return the induced transformation on the domain.

INPUT:

• ieq – list, an inequality. An entry equal to “[-1,7,3,4]” represents the inequality 7x_1+3x_2+4x_3>= 1.

OUTPUT:

• a polyhedron exchange transformation on the subdomain
• a substitution (dict)

EXAMPLES:

sage: from slabbe import PolyhedronExchangeTransformation as PET
sage: base = identity_matrix(2)
sage: translation = vector((1/3, 0))
sage: u = PET.toral_translation(base, translation)


We compute the induced transformation of a polyhedron exchange transformation on a subdomain given by an inequality:

sage: ieq = [1/2, -1, 0]   # x0 <= 1/2
sage: T,sub = u.induced_transformation(ieq)
sage: T
Polyhedron Exchange Transformation of
Polyhedron partition of 3 atoms with 3 letters
with translations {0: (1/3, 0), 1: (-1/3, 0), 2: (0, 0)}
sage: sub
{0: (0,), 1: (0, 1), 2: (0, 0, 1)}

inverse()

Return the inverse of self.

EXAMPLES:

sage: from slabbe import PolyhedronPartition, PolyhedronExchangeTransformation
sage: h = 1/3
sage: p = Polyhedron([(0,0),(h,0),(h,1),(0,1)])
sage: q = Polyhedron([(1,0),(h,0),(h,1),(1,1)])
sage: P = PolyhedronPartition({0:p, 1:q})
sage: T = {0:(1-h,0), 1:(-h,0)}
sage: F = PolyhedronExchangeTransformation(P, T)
sage: F
Polyhedron Exchange Transformation of
Polyhedron partition of 2 atoms with 2 letters
with translations {0: (2/3, 0), 1: (-1/3, 0)}

sage: F.inverse()
Polyhedron Exchange Transformation of
Polyhedron partition of 2 atoms with 2 letters
with translations {0: (-2/3, 0), 1: (1/3, 0)}

merge_atoms_with_same_translation()

Return a new partition into convex polyhedrons where atoms mapped by the same translation are merged if their union is convex.

EXAMPLES:

sage: from slabbe import PolyhedronPartition, PolyhedronExchangeTransformation
sage: h = 1/3
sage: p = Polyhedron([(0,0),(h,0),(h,h),(0,h)])
sage: q = Polyhedron([(0,h),(h,h),(h,1),(0,1)])
sage: r = Polyhedron([(1,0),(h,0),(h,1),(1,1)])
sage: P = PolyhedronPartition({0:p, 1:q, 2:r})
sage: d = {0:(1-h,0), 1:(1-h,0), 2:(-h,0)}
sage: T = PolyhedronExchangeTransformation(P, d)
sage: T
Polyhedron Exchange Transformation of
Polyhedron partition of 3 atoms with 3 letters
with translations {0: (2/3, 0), 1: (2/3, 0), 2: (-1/3, 0)}
sage: T.merge_atoms_with_same_translation()
Polyhedron Exchange Transformation of
Polyhedron partition of 2 atoms with 2 letters
with translations {0: (2/3, 0), 2: (-1/3, 0)}

partition()

EXAMPLES:

sage: from slabbe import PolyhedronPartition, PolyhedronExchangeTransformation
sage: h = 1/3
sage: p = Polyhedron([(0,0),(h,0),(h,1),(0,1)])
sage: q = Polyhedron([(1,0),(h,0),(h,1),(1,1)])
sage: P = PolyhedronPartition({0:p, 1:q})
sage: d = {0:(1-h,0), 1:(-h,0)}
sage: T = PolyhedronExchangeTransformation(P, d)
sage: T.partition()
Polyhedron partition of 2 atoms with 2 letters

plot()

EXAMPLES:

sage: from slabbe import PolyhedronPartition, PolyhedronExchangeTransformation
sage: h = 1/3
sage: p = Polyhedron([(0,0),(h,0),(h,1),(0,1)])
sage: q = Polyhedron([(1,0),(h,0),(h,1),(1,1)])
sage: P = PolyhedronPartition({0:p, 1:q})
sage: d = {0:(1-h,0), 1:(-h,0)}
sage: T = PolyhedronExchangeTransformation(P, d)
sage: T.plot()
Graphics object consisting of 16 graphics primitives

classmethod toral_translation(base, translation, fundamental_domain=None)

Return a polyhedron exchange transformation defined by a translation on a d-dimensional torus.

INPUT:

• base – matrix, the columns are the base of a lattice
• translation – vector, translation vector
• fundamental_domain – polyhedron or None (default: None), if None the parallelotope defined by base is used.

OUTPUT:

a polyhedron exchange transformation on the fundamental domain of the lattice

EXAMPLES:

sage: from slabbe import PolyhedronExchangeTransformation as PET
sage: base = diagonal_matrix((1,1))
sage: translation = vector((1/5, 1/3))
sage: T = PET.toral_translation(base, translation)
sage: T
Polyhedron Exchange Transformation of
Polyhedron partition of 4 atoms with 4 letters
with translations {0: (1/5, 1/3), 1: (1/5, -2/3), 2: (-4/5, 1/3), 3: (-4/5, -2/3)}
sage: T.partition()
Polyhedron partition of 4 atoms with 4 letters


Some preliminary definitions:

sage: z = polygen(QQ, 'z') #z = QQ['z'].0 # same as
sage: K = NumberField(z**2-z-1, 'phi', embedding=RR(1.6))
sage: phi = K.gen()
sage: vertices = ((-phi + 2, phi - 1), (-phi + 2, 1), (phi - 1, 1))
sage: p = Polyhedron(vertices, base_ring=K)


A translation +1 modulo phi on the x coordinate:

sage: base = diagonal_matrix((phi,phi))
sage: translation = vector((1, 0))
sage: t0 = PET.toral_translation(base, translation)
sage: t0
Polyhedron Exchange Transformation of
Polyhedron partition of 2 atoms with 2 letters
with translations {0: (1, 0), 1: (-phi + 1, 0)}
sage: t0(p).vertices()
(A vertex at (-phi + 3, phi - 1),
A vertex at (-phi + 3, 1),
A vertex at (phi, 1))


The inverse map:

sage: t0.inverse()
Polyhedron Exchange Transformation of
Polyhedron partition of 2 atoms with 2 letters
with translations {0: (-1, 0), 1: (phi - 1, 0)}
sage: t0(p) == p
False
sage: t0.inverse()(t0(p)) == p
True


A rotation modulo 1 on the y coordinate:

sage: base = diagonal_matrix((phi,phi))
sage: translation = vector((0, 1))
sage: t1 = PET.toral_translation(base, translation)
sage: t1(p).vertices()
(A vertex at (-phi + 2, 0),
A vertex at (-phi + 2, -phi + 2),
A vertex at (phi - 1, -phi + 2))


It works if the translation is larger than the fundamental domain:

sage: base = diagonal_matrix((1,1))
sage: translation = vector((phi, 0))
sage: t2 = PET.toral_translation(base, translation)
sage: t2(p).vertices()
(A vertex at (0, phi - 1),
A vertex at (0, 1),
A vertex at (2*phi - 3, 1))


The domain is the fundamental domain of the given lattice:

sage: base = diagonal_matrix((phi^-2,1))
sage: translation = vector((phi^-3, 0))
sage: t3 = PET.toral_translation(base, translation)
sage: t3.domain().vertices()
(A vertex at (-phi + 2, 0),
A vertex at (-phi + 2, 1),
A vertex at (0, 0),
A vertex at (0, 1))


The fundamental domain can be given as input. For example, it can be a translated copy of the base parallelotope:

sage: base = diagonal_matrix((1,1))
sage: translation = vector((1/5, 1/3))
sage: F = polytopes.parallelotope(base)
sage: T = PET.toral_translation(base, translation, F-vector((1/10,1/10)))


But it does not always work well yet, for example for other shape of fundamental domains:

sage: m = matrix(2, (1,1,0,1))
sage: T = PET.toral_translation(base, translation, m*F)
Traceback (most recent call last):
...
NotImplementedError: Volume of the partition is 41/45 but the
fundamental domain as volume 1. The code does not handle this
case properly yet.

translations()

EXAMPLES:

sage: from slabbe import PolyhedronPartition, PolyhedronExchangeTransformation
sage: h = 1/3
sage: p = Polyhedron([(0,0),(h,0),(h,1),(0,1)])
sage: q = Polyhedron([(1,0),(h,0),(h,1),(1,1)])
sage: P = PolyhedronPartition({0:p, 1:q})
sage: T = {0:(1-h,0), 1:(-h,0)}
sage: F = PolyhedronExchangeTransformation(P, T)
sage: F.translations()
{0: (2/3, 0), 1: (-1/3, 0)}

class slabbe.polyhedron_partition.PolyhedronPartition(atoms, base_ring=None)

Bases: object

Return a partition into polyhedron.

Note: Many atoms may share the same key.

INPUT:

• atoms – list of polyhedron or dict of key -> polyhedron or list of (key, polyhedron)
• base_ring – base ring (default: None) of the vertices

EXAMPLES:

sage: from slabbe import PolyhedronPartition
sage: h = 1/2
sage: p = Polyhedron([(0,h),(0,1),(h,1)])
sage: q = Polyhedron([(0,0), (0,h), (h,1), (1,1), (1,h), (h,0)])
sage: r = Polyhedron([(h,0), (1,0), (1,h)])
sage: P = PolyhedronPartition([p,q,r])
sage: P
Polyhedron partition of 3 atoms with 3 letters

sage: P.is_pairwise_disjoint()
True
sage: P.volume()
1
sage: G = P.plot()


From a dict:

sage: PolyhedronPartition(dict(a=p,b=q,c=r))
Polyhedron partition of 3 atoms with 3 letters


From a list of (key, polyhedron):

sage: PolyhedronPartition([(9,p),(8,q),(9,r)])
Polyhedron partition of 3 atoms with 2 letters

alphabet()

EXAMPLES:

sage: from slabbe import PolyhedronPartition
sage: h = 1/2
sage: p = Polyhedron([(0,h),(0,1),(h,1)])
sage: q = Polyhedron([(0,0), (0,h), (h,1), (1,1), (1,h), (h,0)])
sage: r = Polyhedron([(h,0), (1,0), (1,h)])
sage: P = PolyhedronPartition([(3,p), (5,q), (9,r)])
sage: P.alphabet()
{3, 5, 9}
sage: P = PolyhedronPartition([(3,p), (5,q), (3,r)])
sage: P.alphabet()
{3, 5}

alphabet_size()

EXAMPLES:

sage: from slabbe import PolyhedronPartition
sage: h = 1/2
sage: p = Polyhedron([(0,h),(0,1),(h,1)])
sage: q = Polyhedron([(0,0), (0,h), (h,1), (1,1), (1,h), (h,0)])
sage: r = Polyhedron([(h,0), (1,0), (1,h)])
sage: P = PolyhedronPartition([(3,p), (5,q), (9,r)])
sage: P.alphabet_size()
3
sage: P = PolyhedronPartition([(3,p), (5,q), (3,r)])
sage: P.alphabet_size()
2

ambient_space()

EXAMPLES:

sage: from slabbe import PolyhedronPartition
sage: h = 1/2
sage: p = Polyhedron([(0,h),(0,1),(h,1)])
sage: q = Polyhedron([(0,0), (0,h), (h,1), (1,1), (1,h), (h,0)])
sage: r = Polyhedron([(h,0), (1,0), (1,h)])
sage: P = PolyhedronPartition([p,q,r])
sage: P.ambient_space()
Vector space of dimension 2 over Rational Field

atoms()

EXAMPLES:

sage: from slabbe import PolyhedronPartition
sage: h = 1/2
sage: p = Polyhedron([(0,h),(0,1),(h,1)])
sage: q = Polyhedron([(0,0), (0,h), (h,1), (1,1), (1,h), (h,0)])
sage: r = Polyhedron([(h,0), (1,0), (1,h)])
sage: P = PolyhedronPartition([p,q,r])
sage: P.atoms()
[A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 3 vertices,
A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 6 vertices,
A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 3 vertices]

base_ring()

EXAMPLES:

sage: from slabbe import PolyhedronPartition
sage: h = 1/2
sage: p = Polyhedron([(0,h),(0,1),(h,1)])
sage: q = Polyhedron([(0,0), (0,h), (h,1), (1,1), (1,h), (h,0)])
sage: r = Polyhedron([(h,0), (1,0), (1,h)])
sage: P = PolyhedronPartition([p,q,r])
sage: P.base_ring()
Rational Field

cached_atoms_set()

EXAMPLES:

sage: from slabbe import PolyhedronPartition
sage: h = 1/2
sage: p = Polyhedron([(0,h),(0,1),(h,1)])
sage: q = Polyhedron([(0,0), (0,h), (h,1), (1,1), (1,h), (h,0)])
sage: r = Polyhedron([(h,0), (1,0), (1,h)])
sage: P = PolyhedronPartition([p,q,r])
sage: P.cached_atoms_set()
{A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 3 vertices,
A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 3 vertices,
A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 6 vertices}

code(p)

Returns in which atom the polyhedron lives in.

INPUT:

• p – a polyhedron

OUTPUT:

integer (for the i-th atom)

EXAMPLES:

sage: from slabbe import PolyhedronPartition
sage: h = 1/3
sage: p = Polyhedron([(0,h),(0,1),(h,1)])
sage: q = Polyhedron([(0,0), (0,h), (h,1), (h,0)])
sage: r = Polyhedron([(h,1), (1,1), (1,h), (h,0)])
sage: s = Polyhedron([(h,0), (1,0), (1,h)])
sage: P = PolyhedronPartition({0:p, 1:q, 2:r, 3:s})
sage: P.code(p)
0
sage: P.code(q)
1
sage: t = Polyhedron([(0, 8/9), (0, 1), (1/9, 1)])
sage: P.code(t)
0


TESTS:

sage: t = Polyhedron([(0, 1/9), (0, 1), (1/9, 1)])
sage: P.code(t)
Traceback (most recent call last):
...
ValueError: polyhedron p whose vertices are (A vertex at (0,
1), A vertex at (0, 1/9), A vertex at (1/9, 1)) lies in no atom

domain()

Return the domain of the partition.

OUTPUT:

a polyhedron

EXAMPLES:

sage: from slabbe import PolyhedronPartition
sage: h = 1/3
sage: p = Polyhedron([(0,0),(h,0),(h,1),(0,1)])
sage: q = Polyhedron([(1,0),(h,0),(h,1),(1,1)])
sage: P = PolyhedronPartition({0:p, 1:q})
sage: P.domain()
A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 4 vertices
sage: P.domain().vertices()
(A vertex at (0, 0),
A vertex at (0, 1),
A vertex at (1, 0),
A vertex at (1, 1))

edges()

Return the edges of partition (one copy of each edge).

Note

If there are vertices of atoms on the interior of the edge of another atom, then, the overlapping edges will be repeated.

OUTPUT:

• set of sorted pair of immutable vectors

EXAMPLES:

sage: from slabbe import PolyhedronPartition
sage: h = 1/2
sage: p = Polyhedron([(0,h),(0,1),(h,1)])
sage: q = Polyhedron([(0,0), (0,h), (h,1), (1,1), (1,h), (h,0)])
sage: r = Polyhedron([(h,0), (1,0), (1,h)])
sage: P = PolyhedronPartition([p,q,r])
sage: sorted(P.edges())
[((0, 0), (0, 1/2)),
((0, 0), (1/2, 0)),
((0, 1/2), (0, 1)),
((0, 1/2), (1/2, 1)),
((0, 1), (1/2, 1)),
((1/2, 0), (1, 0)),
((1/2, 0), (1, 1/2)),
((1/2, 1), (1, 1)),
((1, 0), (1, 1/2)),
((1, 1/2), (1, 1))]


Irrational partition:

sage: z = polygen(QQ, 'z') #z = QQ['z'].0 # same as
sage: K = NumberField(z**2-z-1, 'phi', embedding=RR(1.6))
sage: phi = K.gen()
sage: h = 1/phi^2
sage: p = Polyhedron([(0,h),(0,1),(h,1)])
sage: q = Polyhedron([(0,0), (0,h), (h,1), (h,0)])
sage: r = Polyhedron([(h,1), (1,1), (1,h), (h,0)])
sage: s = Polyhedron([(h,0), (1,0), (1,h)])
sage: P = PolyhedronPartition({0:p, 1:q, 2:r, 3:s}, base_ring=K)
sage: sorted(P.edges())
[((0, 0), (0, -phi + 2)),
((0, 0), (-phi + 2, 0)),
((0, -phi + 2), (0, 1)),
((0, -phi + 2), (-phi + 2, 1)),
((0, 1), (-phi + 2, 1)),
((-phi + 2, 0), (-phi + 2, 1)),
((-phi + 2, 0), (1, 0)),
((-phi + 2, 0), (1, -phi + 2)),
((-phi + 2, 1), (1, 1)),
((1, 0), (1, -phi + 2)),
((1, -phi + 2), (1, 1))]

is_pairwise_disjoint()

Return whether atoms of the partition are pairwise disjoint.

EXAMPLES:

sage: from slabbe import PolyhedronPartition
sage: h = 1/2
sage: p = Polyhedron([(0,h),(0,1),(h,1)])
sage: q = Polyhedron([(0,0), (0,h), (h,1), (1,1), (1,h), (h,0)])
sage: r = Polyhedron([(h,0), (1,0), (1,h)])
sage: P = PolyhedronPartition([p,q,r])
sage: P.is_pairwise_disjoint()
True

keys_permutation(other)

Return a relabelling permutation of the keys for self to look like other.

Note

currently, the code works only if the coding of self and other is injective, i.e., no two polyhedron are coded by the same letter.

INPUT:

• other – a polyhedron partition (with injective coding)

OUTPUT:

dict, key -> key

EXAMPLES:

sage: from slabbe import PolyhedronPartition
sage: h = 1/2
sage: p = Polyhedron([(0,h),(0,1),(h,1)])
sage: q = Polyhedron([(0,0), (0,h), (h,1), (1,1), (1,h), (h,0)])
sage: r = Polyhedron([(h,0), (1,0), (1,h)])
sage: P = PolyhedronPartition({4:p, 1:q, 2:r})
sage: Q = PolyhedronPartition({0:p, 5:q})
sage: d = P.keys_permutation(Q)
sage: d
{1: 5, 2: 1, 4: 0}
sage: P.rename_keys(d)
Polyhedron partition of 3 atoms with 3 letters

keys_permutation_lexicographic()

Return a permutation relabelling of the keys for self in increasing order for the lexicographic order of the centers of the polyhedrons.

OUTPUT:

dict, key -> key

EXAMPLES:

sage: from slabbe import PolyhedronPartition
sage: h = 1/2
sage: p = Polyhedron([(0,h),(0,1),(h,1)])
sage: q = Polyhedron([(0,0), (0,h), (h,1), (1,1), (1,h), (h,0)])
sage: r = Polyhedron([(h,0), (1,0), (1,h)])
sage: P = PolyhedronPartition({4:p, 1:q, 2:r})
sage: d = P.keys_permutation_lexicographic()
sage: d
{1: 1, 2: 2, 4: 0}
sage: P.rename_keys(d)
Polyhedron partition of 3 atoms with 3 letters

sage: Q = PolyhedronPartition({0:p, 5:q})
sage: Q.keys_permutation_lexicographic()
{0: 0, 5: 1}


It works when the partition has two atoms coded by the same key:

sage: P = PolyhedronPartition([(0,p), (0,q), (3,r)])
sage: d = P.keys_permutation_lexicographic()
sage: d
{0: 0, 3: 1}
sage: P.rename_keys(d).alphabet()
{0, 1}

merge_atoms(d)

Return the polyhedron partition obtained by merging atoms having the same image under the dictionnary.

INPUT:

• d – dict

OUTPUT:

a polyhedron partition

EXAMPLES:

sage: from slabbe import PolyhedronPartition
sage: h = 1/2
sage: p = Polyhedron([(0,h),(0,1),(h,1)])
sage: q = Polyhedron([(0,0), (0,h), (h,1), (1,1), (1,h), (h,0)])
sage: r = Polyhedron([(h,0), (1,0), (1,h)])
sage: P = PolyhedronPartition({0:p, 1:q, 2:r})
sage: P.merge_atoms({0:4, 1:4, 2:5})
Polyhedron partition of 2 atoms with 2 letters
sage: P.merge_atoms({0:4, 1:5, 2:4})
Polyhedron partition of 3 atoms with 2 letters


When pair of atoms are not convex, it needs to merge 3 or more atoms:

sage: h = 1/5
sage: p = Polyhedron([(0,0),(h,1-h),(0,1)])
sage: q = Polyhedron([(0,1), (h,1-h), (1,1)])
sage: r = Polyhedron([(0,0), (h,1-h), (1,1), (1,0)])
sage: P = PolyhedronPartition({0:p, 1:q, 2:r})
sage: P.merge_atoms({0:4, 1:4, 2:4})
Polyhedron partition of 1 atoms with 1 letters

plot()

EXAMPLES:

sage: from slabbe import PolyhedronPartition
sage: h = 1/2
sage: p = Polyhedron([(0,h),(0,1),(h,1)])
sage: q = Polyhedron([(0,0), (0,h), (h,1), (1,1), (1,h), (h,0)])
sage: r = Polyhedron([(h,0), (1,0), (1,h)])
sage: P = PolyhedronPartition([p,q,r])
sage: P.plot()
Graphics object consisting of 21 graphics primitives

refine_by_hyperplane(ieq)

Refine the partition with the two half spaces of each side of an hyperplane.

INPUT:

• ieq – list, an inequality. An entry equal to “[-1,7,3,4]” represents the inequality 7x_1+3x_2+4x_3>= 1.

EXAMPLES:

sage: from slabbe import PolyhedronPartition
sage: h = 1/3
sage: p = Polyhedron([(0,h),(0,1),(h,1)])
sage: q = Polyhedron([(0,0), (0,h), (h,1), (h,0)])
sage: r = Polyhedron([(h,1), (1,1), (1,h), (h,0)])
sage: s = Polyhedron([(h,0), (1,0), (1,h)])
sage: P = PolyhedronPartition({0:p, 1:q, 2:r, 3:s})
sage: ieq = [-4, 5, 1]
sage: P.refine_by_hyperplane(ieq)
Polyhedron partition of 6 atoms with 6 letters

refinement(other, key_fn=None)

Return the polyhedron partition obtained by the intersection of the atoms of self with the atoms of other.

Only atoms of positive volume are kept.

INPUT:

• other – a polyhedron partition
• key_fn – function to apply on pairs of labels, or None

OUTPUT:

a polyhedron partition

EXAMPLES:

sage: from slabbe import PolyhedronPartition
sage: h = 1/3
sage: p = Polyhedron([(0,h),(0,1),(h,1)])
sage: q = Polyhedron([(0,0), (0,h), (h,1), (h,0)])
sage: r = Polyhedron([(h,1), (1,1), (1,h), (h,0)])
sage: s = Polyhedron([(h,0), (1,0), (1,h)])
sage: P = PolyhedronPartition({0:p, 1:q, 2:r, 3:s})
sage: g = 1/5
sage: t1 = Polyhedron([(g,g), (g,1-g), (1-g,g) ])
sage: t2 = Polyhedron([(g,1-g), (1-g,g), (1-g,1-g)])
sage: Q = PolyhedronPartition([t1,t2])
sage: P.refinement(Q)
Polyhedron partition of 8 atoms with 8 letters

rename_keys(d)

Return a polyhedron partition whose keys are the images under a map.

INPUT:

• d – dict, function old key -> new key

EXAMPLES:

sage: from slabbe import PolyhedronPartition
sage: h = 1/2
sage: p = Polyhedron([(0,h),(0,1),(h,1)])
sage: q = Polyhedron([(0,0), (0,h), (h,1), (1,1), (1,h), (h,0)])
sage: r = Polyhedron([(h,0), (1,0), (1,h)])
sage: P = PolyhedronPartition([p,q,r])
sage: Q = P.rename_keys({0:'b', 1:'a', 2:'z'})
sage: Q
Polyhedron partition of 3 atoms with 3 letters
sage: sorted(key for key,p in Q)
['a', 'b', 'z']


It does not have to be injective:

sage: Q = P.rename_keys({0:'b', 1:'a', 2:'b'})
sage: sorted(key for key,p in Q)
['a', 'b', 'b']

tikz(fontsize='\\normalsize', scale=1, label_format='{}', extra_code='')

INPUT:

• fontsize – string (default: r'\normalsize'
• scale – number (default: 1)
• label_format – string (default: r'{}') to be called with label_format.format(key)
• extra_code – string (default: '')

EXAMPLES:

sage: from slabbe import PolyhedronPartition
sage: h = 1/2
sage: p = Polyhedron([(0,h),(0,1),(h,1)])
sage: q = Polyhedron([(0,0), (0,h), (h,1), (1,1), (1,h), (h,0)])
sage: r = Polyhedron([(h,0), (1,0), (1,h)])
sage: P = PolyhedronPartition([p,q,r])
sage: _ = P.tikz().pdf(view=False)


Irrational partition:

sage: z = polygen(QQ, 'z') #z = QQ['z'].0 # same as
sage: K = NumberField(z**2-z-1, 'phi', embedding=RR(1.6))
sage: phi = K.gen()
sage: h = 1/phi^2
sage: p = Polyhedron([(0,h),(0,1),(h,1)])
sage: q = Polyhedron([(0,0), (0,h), (h,1), (h,0)])
sage: r = Polyhedron([(h,1), (1,1), (1,h), (h,0)])
sage: s = Polyhedron([(h,0), (1,0), (1,h)])
sage: P = PolyhedronPartition({0:p, 1:q, 2:r, 3:s}, base_ring=K)
sage: _ = P.tikz().pdf(view=False)


Testing the options:

sage: _ = P.tikz(fontsize=r'\scriptsize').pdf(view=False)
sage: _ = P.tikz(scale=2).pdf(view=False)
sage: _ = P.tikz(label_format=r'$a_{{{}}}$').pdf(view=False)

translation(displacement)

Return the translated partition of polyhedron.

INPUT:

• displacement – a displacement vector or a list/tuple of coordinates that determines a displacement vector.

OUTPUT:

The translated partition.

EXAMPLES:

sage: from slabbe import PolyhedronPartition
sage: h = 1/2
sage: p = Polyhedron([(0,h),(0,1),(h,1)])
sage: q = Polyhedron([(0,0), (0,h), (h,1), (1,1), (1,h), (h,0)])
sage: r = Polyhedron([(h,0), (1,0), (1,h)])
sage: P = PolyhedronPartition([p,q,r])
sage: P.translation((1,1))
Polyhedron partition of 3 atoms with 3 letters

volume()

EXAMPLES:

sage: from slabbe import PolyhedronPartition
sage: h = 1/2
sage: p = Polyhedron([(0,h),(0,1),(h,1)])
sage: q = Polyhedron([(0,0), (0,h), (h,1), (1,1), (1,h), (h,0)])
sage: r = Polyhedron([(h,0), (1,0), (1,h)])
sage: P = PolyhedronPartition([p,q,r])
sage: P.volume()
1


TESTS:

sage: PolyhedronPartition([], base_ring=ZZ).volume()
0

volume_dict(normalize=False)

INPUT

• normalize – boolean (default:False), whether to normalize the sum of the whole volume to 1

EXAMPLES:

sage: from slabbe import PolyhedronPartition
sage: h = 1/2
sage: p = Polyhedron([(0,h),(0,1),(h,1)])
sage: q = Polyhedron([(0,0), (0,h), (h,1), (1,1), (1,h), (h,0)])
sage: r = Polyhedron([(h,0), (1,0), (1,h)])
sage: P = PolyhedronPartition([p,q,r])
sage: P.volume_dict()
{0: 1/8, 1: 3/4, 2: 1/8}
sage: (2*P).volume_dict()
{0: 1/2, 1: 3, 2: 1/2}

slabbe.polyhedron_partition.find_unused_key(d, sequence)

Return the first key in sequence which is not in d.

EXAMPLES:

sage: from slabbe.polyhedron_partition import find_unused_key
sage: d = {3:32, 0:21, 1:4, 5:5}
sage: find_unused_key(d, NN)
2
sage: d[2] = 1234
sage: find_unused_key(d, NN)
4
sage: d[4] = 1234
sage: find_unused_key(d, NN)
6

slabbe.polyhedron_partition.is_union_convex(t)

Return whether the union of the polyhedrons is convex.

INPUT:

• t – list of polyhedron

EXAMPLES:

sage: from slabbe.polyhedron_partition import is_union_convex
sage: h = 1/2
sage: p = Polyhedron([(0,h),(0,1),(h,1)])
sage: q = Polyhedron([(0,0), (0,h), (h,1), (1,1), (1,h), (h,0)])
sage: r = Polyhedron([(h,0), (1,0), (1,h)])
sage: is_union_convex((p,q,r))
True
sage: is_union_convex((p,q))
True
sage: is_union_convex((p,r))
False


Here we need to consider the three at the same time to get a convex union:

sage: h = 1/5
sage: p = Polyhedron([(0,0),(h,1-h),(0,1)])
sage: q = Polyhedron([(0,1), (h,1-h), (1,1)])
sage: r = Polyhedron([(0,0), (h,1-h), (1,1), (1,0)])
sage: is_union_convex((p,q))
False
sage: is_union_convex((p,r))
False
sage: is_union_convex((q,r))
False
sage: is_union_convex((p,q,r))
True