Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Buchtitelbild

2015 | OriginalPaper | Buchkapitel

An Optimal Algorithm for Tiling the Plane with a Translated Polyomino

verfasst von : Andrew Winslow

Erschienen in: Algorithms and Computation

Verlag: Springer Berlin Heidelberg

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

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.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren
Nächstes Kapitel Adaptive Point Location in Planar Convex Subdivisions
Literatur
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.
Golomb, S.W.: Polyominoes. Scribner’s, New York (1965) MATH
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.
Shapiro, H.D.: Theoretical limitations on the efficient use of parallel memories. IEEE Trans. Comput. 27(5), 421–428 (1978)MathSciNetCrossRefMATH
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
Metadaten
Titel
An Optimal Algorithm for Tiling the Plane with a Translated Polyomino
verfasst von
Andrew Winslow
Copyright-Jahr
2015
Verlag
Springer Berlin Heidelberg
Buch
Algorithms and Computation

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

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

Copyright-Jahr: 2015

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