×

zbMATH — the first resource for mathematics

Tilings robust to errors. (English) Zbl 1283.52018
López-Ortiz, Alejandro (ed.), LATIN 2010: Theoretical informatics. 9th Latin American symposium, Oaxaca, Mexico, April 19–23, 2010. Proceedings. Berlin: Springer (ISBN 978-3-642-12199-9/pbk). Lecture Notes in Computer Science 6034, 480-491 (2010).
Summary: We study the error robustness of tilings of the plane. The fundamental question is the following: given a tileset, what happens if we allow a small probability of errors? Are the objects we obtain close to an error-free tiling of the plane?
We prove that tilesets that produce only periodic tilings are robust to errors. For this proof, we use a hierarchical construction of islands of errors (see, e.g. [B. Durand et al., Lect. Notes Comput. Sci. 5257, 276–288 (2008; Zbl 1161.68033)]). We also show that another class of tilesets, those that admit countably many tilings is not robust and that there is no computable way to distinguish between these two classes.
For the entire collection see [Zbl 1185.68011].

MSC:
52B55 Computational aspects related to convexity
52C22 Tilings in \(n\) dimensions (aspects of discrete geometry)
PDF BibTeX XML Cite
Full Text: DOI