Pavages aléatoires

Il devient de plus en plus difficile de choisir un carrelage original pour sa salle de bains.

Depuis le XVème siècle, 17 types de pavages réguliers différents sont utilisés dans les décorations de l'Alhambra. En 1891, le mathématicien russe Evgraf Fedorov démontre que le nombre de pavages réguliers distincts  vaut ... 17 [1].  Et ce n'est qu'entre 1968 et 1984 qu'on parvient à classifier toutes les formes de pavés possibles en 19 catégories [2]. Depuis, les carreleurs ne peuvent se distinguer que par des motifs et des couleurs, plus par la géométrie.

En 1974, le pavage quasi-périodique de Penrose crée un choc : il est possible de recouvrir le plan avec des pavés de deux formes différentes arrangés selon des règles rigoureuses, mais ne générant pas de motif périodique. En 1994, Radin et Conway en proposent un autre, le "Pinwheel tiling". Voilà pour le XXème siècle.

En 2011, c'est John Shier, un "artiste algorithmique" qui vient d'ouvrir tout grand la porte à une infinité de nouveaux pavages. Sa méthode permettent de couvrir le plan avec des pavés de presque n'importe quelles formes, mais de surface décroissantes [3,4]. Le principe semble tout simple : on place le plus grand pavé au hasard, puis le suivant en taille au hasard dans une surface libre et ainsi de suite.

Le pavage de John Shier le plus simple

Le problème est que si on réduit la taille des pavés trop vite on ne recouvre pas tout le plan, et si on réduit trop lentement, on risque d'être "coincé" à ne pas pouvoir placer un pavé. L'astuce consiste à attribuer au i-ème pavé une surface de A₀/i^c. Dans ce cas, la surface totale vaut :

$latex A_{total} = A_{0} \sum_{i=0}^{\infty } i^{-c}$

On reconnait en passant la fonction zêta de Riemann, qui converge pour c>1. Grâce à cette formule, une fois choisi un c, la formule permet de calculer la surface A₀ qui garantit qu'il ne restera plus un seul espace libre après avoir placé une infinité de pavés. En pratique on obtient d'excellent remplissages avec quelques milliers de pavés, un peu de patience et un bon programme. Paul Bourque décrit tout ceci en détail sur une page [5] agrémentée de magnifiques exemples:

Il a même étendu la méthode à la 3D :

Pour ma part, j'ai réalisé la petite application ci-dessous en Processing (disponible aussi sur OpenProcessing avec son code source) pour expérimenter un peu cet algorithme que je trouve spectaculaire: