Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Cover of the book

2015 | OriginalPaper | Chapter

An Optimal Algorithm for Tiling the Plane with a Translated Polyomino

Author : Andrew Winslow

Published in: Algorithms and Computation

Publisher: Springer Berlin Heidelberg

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

We give a O(n)-time algorithm for determining whether translations of a polyomino with n edges can tile the plane. The algorithm is also a O(n)-time algorithm for enumerating all regular tilings, and we prove that at most \(\varTheta (n)\) such tilings exist.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
next chapter Adaptive Point Location in Planar Convex Subdivisions
Literature
1.
2.
Berger, R.: The undecidability of the domino problem. In: Memoirs of the American Mathematical Society, vol. 66 (1966)
3.
Brlek, S., Provençal, X.: An optimal algorithm for detecting pseudo-squares. In: Kuba, A., Nyúl, L.G., Palágyi, K. (eds.) DGCI 2006. LNCS, vol. 4245, pp. 403–412. Springer, Heidelberg (2006) CrossRef
4.
Brlek, S., Provençal, X., Fédou, J.-M.: On the tiling by translation problem. Discrete Appl. Math. 157, 464–475 (2009)
5.
6.
Gambini, L., Vuillon, L.: An algorithm for deciding if a polyomino tiles the plane by translations. RAIRO - Theor. Inf. Appl. 41(2), 147–155 (2007)CrossRefMATH
7.
Girault-Beauquier, D., Nivat., M.: Tiling the plane with one tile. In: 6th Annual Symposium on Computational Geometry, pp. 128–138 (1990)
8.
9.
10.
11.
12.
Gusfield, D.: Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology. Cambridge University Press, Cambridge (1997) CrossRefMATH
13.
14.
Blondin-Massé, A., Brlek, S., Garon, A., Labbé, S.: Christoffel and Fibonacci tiles. In: Brlek, S., Reutenauer, C., Provençal, X. (eds.) DGCI 2009. LNCS, vol. 5810, pp. 67–78. Springer, Heidelberg (2009) CrossRef
15.
Massé, A.B., Brlek, S., Garon, A., Labbé, S.: Every polyomino yields at most two square tilings. In: 7th International Conference on Lattice Paths and Applications (Lattice Paths 2010), pp. 57–61 (2010)
16.
Masseé, A.B., Brlek, S., Labbé, S.: Combinatorial aspects of Escher tilings. In: 22nd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2010), pp. 533–544 (2010)
17.
Ollinger, N.: Tiling the plane with a fixed number of polyominoes. In: Dediu, A.H., Ionescu, A.M., Martín-Vide, C. (eds.) LATA 2009. LNCS, vol. 5457, pp. 638–647. Springer, Heidelberg (2009) CrossRef
18.
Provençal, X.: Combinatoire des mots, géométrie discrète et pavages. Ph. D. thesis, Université du Québec à Montréal (2008)
19.
Schattschneider, D.: Will it tile? Try the Conway criterion!. Math. Monthly 53(4), 224–233 (1980)MathSciNetMATH
20.
Schattschneider, D.: Visions of Symmetry: Notebooks, Periodic Drawings, and Related Work of M.C. Escher. W. H. Freeman and Company, New York (1990)
21.
22.
Wijshoff, H.A.G., van Leeuwen, J.: Arbitrary versus periodic storage schemes and tessellations of the plane using one type of polyomino. Inf. Control 62, 1–25 (1984)MathSciNetCrossRefMATH
Metadata
Title
An Optimal Algorithm for Tiling the Plane with a Translated Polyomino
Author
Andrew Winslow
Copyright Year
2015
Publisher
Springer Berlin Heidelberg
Book
Algorithms and Computation

Print ISBN: 978-3-662-48970-3

Electronic ISBN: 978-3-662-48971-0

Copyright Year: 2015

DOI
https://doi.org/10.1007/978-3-662-48971-0_1

Premium Partner

    Image Credits