Distances on Lozenge Tilings

Olivier Bodini (1) , Thomas Fernique (2) , Éric Rémila (3)

1 APR - Algorithmes, Programmes et Résolution
2 ARITH - Arithmétique informatique
3 LIP - Laboratoire de l'Informatique du Parallélisme

In this paper, a structural property of the set of lozenge tilings of a 2n-gon is highlighted. We introduce a simple combinatorial value called Hamming-distance, which is a lower bound for the flipdistance (i.e. the number of necessary local transformations involving three lozenges) between two given tilings. It is here proven that, for n<5, the flip-distance between two tilings is equal to the Hamming-distance. Conversely, for n>5, We show that there is some deficient pairs of tilings for which the flip connection needs more flips than the combinatorial lower bound indicates.

Mots clés: tiling

Domaines: Mathématique discrète [cs.DM]; Combinatoire [math.CO]; Algorithme et structure de données [cs.DS]

Olivier Bodini, Thomas Fernique, Éric Rémila. Distances on Lozenge Tilings. DGCI 2009 - 15th IAPR International Conference on Discrete Geometry for Computer Imagery, Sep 2009, Montreal, Canada. pp.240-251, ⟨10.1007/978-3-642-04397-0_21⟩. ⟨hal-00432218⟩