The project I made for the end of my double bachelor's degree in mathematics and computer science. This is an implementation of the tiling algorithm of a polygon by dominoes in the plane. Described the first time in [2], the implementation is based on the paper of E. Rémilia [1]. The GUI was handmade and the important algorithms are in the algorithms directory.
To generate a tiling, the algorithm use a bijection between the set of tiling of a polygon and a set of height function defined on the polygon. The term of height function comes from [2]. Hence the algorithm try to build a well defined height function given a polygon and the tiling is constructed afterwards. If the algorithm fail to build a well defined height function, this tell that the polygon is non tilleable. All the mathematical details can be found in [1].
| A polygon | A height function |
|---|---|
 |
 |
Using the lattice structure of set of the tilings of a given polygon and the flips between two dominoes (see [1]), one can generate a random tiling using the one given by the algorithm. There is three algorithms implemented to achieve this, two using random walk on the set of tilings and one using a coupling technique similar to the Propp-Wilson algorithm. With these we can observe some phenomenom like the article circle of the aztec diamond. Here are some example generated with the logiciel :
| Aztec Diamond | Hearth shape | Cross shape |
|---|---|---|
 |
 |
 |
You can use the program with the jar provided or by compiling the sources yourself.
It allows you to enter any polygon by describing his boundary. You can use the letters h, d, b and g (respictively for up, right, bottom and left) and exponentitation to describe the boundary. For example the 4x4 square could be described as d^4 h^4 g^4 bbbb, white spaces being ignored. The polygon's boundary of the above images can be found here.
Once you have a polygon you can:
- edit his boundary by double clicking on it in the left panel
- show his tiling and/or his associated height function using the "Affichage" menu at the top
- do flip on his tiling by clicking between two dominoes in the right panel
- generate a random tiling using the "Mélange" menu.
Note that if a polygon is non tilleable and the options to show his tilling is enabled, nothing will be shown in the right panel.
[1] Eric Rémila, The lattice structure of the set of domino tilings of a polygon, Theoretical Computer Science 322, (2004)
[2] J. H. Conway and J. C. Lagarias, Tiling with polyominoes and combinatorial group theory, The American Mathematical Monthly Vol. 97, (1990)