Lozenge Tiling by Computing Distances
Favreau Jean-Marie, Gerard Yan, Lafourcade Pascal, Robert Léo · 2026
Read Lozenge Tiling by Computing Distances by Favreau Jean-Marie, Gerard Yan, Lafourcade Pascal, Robert Léo (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-02476.txt.
Description
Favreau Jean-Marie, Gerard Yan, Lafourcade Pascal, and Robert Léo solve a tiling puzzle in polynomial time in this 2026 paper. The Calisson puzzle fills a hexagon of triangles with lozenge tiles. Some edges are prescribed as tile boundaries, and neighbors across them must tilt differently. No fast algorithm was known for this recent game.
Their advancing surface algorithm runs in cubic time in the hexagon's side length. It can even be run by hand with pencil and eraser. The method reframes classic height function ideas from Conway and Thurston. Tilings lift to stepped surfaces, and heights solve a system of difference constraints. A graph layer makes the hidden algorithmic structure explicit. A region is tilable exactly when its weighted graph has no negative cycle.
Catalog record
| CREATOR | Favreau Jean-Marie, Gerard Yan, Lafourcade Pascal, Robert Léo |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 64802 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.02476