# Polyhedron partition¶

Polyhedron partitions

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()


AUTHORS:

• Sébastien Labbé, November 2017, initial version of polyhedron partitions
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

apply_linear_map(M)

INPUT:

• M – a matrix

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})


Vertical symmetry:

sage: M = diagonal_matrix((-1,1))
sage: P = P.apply_linear_map(M)
sage: P = P.translation((1,0))
sage: P
Polyhedron partition of 4 atoms with 4 letters

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

classmethod jeandel_rao_tilings_partition(backend=None)

This construct the polygon partition associated to Jeandel-Rao tilings introduced in [Lab2019].

INPUT:

• backend – string, polyhedron backend

EXAMPLES:

sage: from slabbe import PolyhedronPartition
sage: P0 = PolyhedronPartition.jeandel_rao_tilings_partition()
sage: P0.is_pairwise_disjoint()
True
sage: P0.volume()
4*phi + 1


The volume is consistent with:

sage: z = polygen(QQ, 'z')
sage: K = NumberField(z**2-z-1, 'phi', embedding=RR(1.6))
sage: phi = K.gen()
sage: phi * (phi + 3)
4*phi + 1


REFERENCES:

 [Lab2019] (1, 2) S. Labbé. A Markov partition for Jeandel-Rao aperiodic Wang tilings. March 2019. https://arxiv.org/abs/1903.06137
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']

classmethod self_similar_19_tiles_partition()

This construct the polygon partition introduced in [Lab2019] associated to the self-similar 19 Wang tiles [Lab2018].

EXAMPLES:

sage: from slabbe import PolyhedronPartition
sage: PU = PolyhedronPartition.self_similar_19_tiles_partition()
sage: PU.is_pairwise_disjoint()
True
sage: PU.volume()
1


REFERENCES:

 [Lab2018] S. Labbé. A self-similar aperiodic set of 19 Wang tiles. Geom. Dedicata, 2018. https://doi.org/10.1007/s10711-018-0384-8.
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