Generalized Tiling with Height Functions

Abstract : 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 poly-ominoes 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.
Type de document :
Article dans une revue
Morfismos, Departamento de Matematicas del CINVESTAV, 2003, 7 (1), pp.47-68
Liste complète des métadonnées

Littérature citée [17 références]  Voir  Masquer  Télécharger

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00269836
Contributeur : Christine Carvalho de Matos <>
Soumis le : mercredi 4 avril 2018 - 17:59:51
Dernière modification le : jeudi 24 mai 2018 - 15:59:21

Fichier

poten2.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : lirmm-00269836, version 1

Collections

Citation

Olivier Bodini, Matthieu Latapy. Generalized Tiling with Height Functions. Morfismos, Departamento de Matematicas del CINVESTAV, 2003, 7 (1), pp.47-68. 〈lirmm-00269836〉

Partager

Métriques

Consultations de la notice

91

Téléchargements de fichiers

17