Generalized Tilings with Height Functions
Résumé
In this paper, we introduce a generalization of a class of tilings which appear in the literature: the tilings over which a height function can be defined (for example, the famous tilings of polyominoes with dominoes). We show that many properties of these tilings can be seen as the consequences of properties of the generalized tilings we introduce. In particular, we show that any tiling problem which can be modelized in our generalized framework has the following properties: the tilability of a region can be constructively decided in polynomial time, the number of connected components in the undirected flip-accessibility graph can be determined, and the directed flip-accessibility graph induces a distributive lattice structure. Finally, we give a few examples of known tiling problems which can be viewed as particular cases of the new notions we introduce.
Nous introduisons dans cet article une casse général de pavages : les pavages sur lesquels une fonction hauteur peut être définie ( par exemple, le célèbre pavage des polyominos par des dominos). Nous montrons que la plupart des propriétés de ces pavages peuvent être vus des conséquences des propriétés des pavages généraux que nous introduisons. En particulier, nous montrons que tout pavage que l'ion peut modéliser dans notre cadre généralisé a les propriétés suivantes : la pavabilité d'une région peut être décidée en temps polynômial, le nombre de composantes connexes dans le graphe non orienté d'accessibilité par flip peut être déterminé algorithmiquement, et le graphe orienté d'accessibilité par flip a une structure de réseau distributif. Pour conclure, nous donnons quelques exemples de problèmes de pavages classiques que l'on peut voir comme des cas particuliers de la nouvelles classes que nous avons définies.
| Origine | Fichiers produits par l'(les) auteur(s) |
|---|