Computer Science – Discrete Mathematics
Scientific paper
2009-11-14
Theor. Comput. Sci. 412(36): 4787-4794 (2011)
Computer Science
Discrete Mathematics
18 pages, 9 figures, submitted to Theoretical Computer Science (special issue of DGCI'09)
Scientific paper
10.1016/j.tcs.2011.04.015
The rhombus tilings of a simply connected domain of the Euclidean plane are known to form a flip-connected space (a flip is the elementary operation on rhombus tilings which rotates 180{\deg} a hexagon made of three rhombi). Motivated by the study of a quasicrystal growth model, we are here interested in better understanding how "tight" rhombus tiling spaces are flip-connected. We introduce a lower bound (Hamming-distance) on the minimal number of flips to link two tilings (flip-distance), and we investigate whether it is sharp. The answer depends on the number n of different edge directions in the tiling: positive for n=3 (dimer tilings) or n=4 (octogonal tilings), but possibly negative for n=5 (decagonal tilings) or greater values of n. A standard proof is provided for the n=3 and n=4 cases, while the complexity of the n=5 case led to a computer-assisted proof (whose main result can however be easily checked by hand).
Bodini Olivier
Fernique Thomas
Rao Michaël
Remila Eric
No associations
LandOfFree
Distances on Rhombus Tilings does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Distances on Rhombus Tilings, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Distances on Rhombus Tilings will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-323492