Generalized tiling with height functions



Título del documento: Generalized tiling with height functions
Revista: Morfismos
Base de datos: PERIÓDICA
Número de sistema: 000223149
Autores: 1
2
Instituciones: 1Universite de Montpellier II (Sciences et Techniques), Laboratoire d'Informatique, de Robotique et de Microelectronique de Montpellier, Montpellier, Herault. Francia
2Universite de Paris VII (Denis Diderot), Laboratoire d'Informatique Algorithmique: Fondements et Applications, París. Francia
Año:
Periodo: Jun
Volumen: 7
Número: 1
Paginación: 47-68
País: México
Idioma: Inglés
Tipo de documento: Artículo
Enfoque: Aplicado
Resumen en inglés 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
Disciplinas: Matemáticas
Palabras clave: Matemáticas puras,
Geometría,
Combinatoria,
Teselado,
Retículas distributivas,
Muestreo aleatorio
Keyword: Mathematics,
Pure mathematics,
Geometry,
Combinatorics,
Tessellation,
Distributive lattices,
Random sampling
Texto completo: Texto completo (Ver PDF)