Service interruption on Monday 11 July from 12:30 to 13:00: all the sites of the CCSD (HAL, EpiSciences, SciencesConf, AureHAL) will be inaccessible (network hardware connection).
Skip to Main content Skip to Navigation

Generalized Tilings 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 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.
Document type :
Complete list of metadata
Contributor : Colette ORANGE Connect in order to contact the contributor
Submitted on : Wednesday, April 17, 2019 - 9:14:19 AM
Last modification on : Monday, October 11, 2021 - 1:48:02 PM


Files produced by the author(s)


  • HAL Id : hal-02102104, version 1



Olivier Bodini, Matthieu Latapy. Generalized Tilings with Height Functions. [Research Report] LIP RR-2001-52, Laboratoire de l'informatique du parallélisme. 2001, 2+17p. ⟨hal-02102104⟩



Record views


Files downloads