Document Open Access Logo

A Quasilinear-Time Algorithm for Tiling the Plane Isohedrally with a Polyomino

Authors Stefan Langerman, Andrew Winslow

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2016.50.pdf
  • Filesize: 0.57 MB
  • 15 pages

Document Identifiers

Author Details

Stefan Langerman
Andrew Winslow

Cite AsGet BibTex

Stefan Langerman and Andrew Winslow. A Quasilinear-Time Algorithm for Tiling the Plane Isohedrally with a Polyomino. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 50:1-50:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.SoCG.2016.50

Abstract

A plane tiling consisting of congruent copies of a shape is isohedral provided that for any pair of copies, there exists a symmetry of the tiling mapping one copy to the other. We give a O(n*log^2(n))-time algorithm for deciding if a polyomino with n edges can tile the plane isohedrally. This improves on the O(n^{18})-time algorithm of Keating and Vince and generalizes recent work by Brlek, Provençal, Fédou, and the second author.
Keywords
  • Plane tiling
  • polyomino
  • boundary word
  • isohedral

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. N. Alon, R. Yuster, and U. Zwick. Finding and counting given length cycles. Algorithmica, 17(3):209-223, 1997. Google Scholar
  2. A. Apostolico, D. Breslauer, and Z. Galil. Parallel detection of all palindromes in a string. Theoretical Computer Science, 141:163-173, 1995. Google Scholar
  3. D. Beauquier and M. Nivat. On translating one polyomino to tile the plane. Discrete &Computational Geometry, 6:575-592, 1991. Google Scholar
  4. S. Brlek, M. Koskas, and X. Provençal. A linear time and space algorithm for detecting path intersection. In DGCI 2009, volume 5810 of LNCS, pages 397-408. Springer Berlin Heidelberg, 2009. Google Scholar
  5. S. Brlek, J.-M. X. Provençal, and Fédou. On the tiling by translation problem. Discrete Applied Mathematics, 157:464-475, 2009. Google Scholar
  6. M. Crochemore and W. Rytter. Text Algorithms. Oxford University Press, 1994. Google Scholar
  7. A. Daurat and M. Nivat. Salient and reentrant points of discrete sets. Discrete Applied Mathematics, 151:106-121, 2005. Google Scholar
  8. N. J. Fine and H. S. Wilf. Uniqueness theorems for periodic functions. Proceedings of the American Mathematical Society, 16:109-114, 1965. Google Scholar
  9. Z. Galil and J. Seiferas. A linear-time on-line recognition algorithm for "Palstar". Journal of the ACM, 25(1):102-111, 1978. Google Scholar
  10. L. Gambini and L. Vuillon. An algorithm for deciding if a polyomino tiles the plane by translations. RAIRO - Theoretical Informatics and Applications, 41(2):147-155, 2007. Google Scholar
  11. M. Gardner. More about tiling the plane: the possibilities of polyominoes, polyiamonds, and polyhexes. Scientific American, pages 112-115, August 1975. Google Scholar
  12. C. Goodman-Strauss. Open questions in tiling. Online, published 2000. URL: http://comp.uark.edu/~strauss/papers/survey.pdf.
  13. C. Goodman-Strauss. Can't decide? undecide! Notices of the American Mathematical Society, 57(3):343-356, 2010. Google Scholar
  14. B. Grünbaum and G. C. Shephard. The eighty-one types of isohedral tilings in the plane. Mathematical Proceedings of the Cambridge Philosophical Society, 82(2):177-196, 1977. Google Scholar
  15. B. Grünbaum and G. C. Shephard. Isohedral tilings of the plane by polygons. Commentarii Mathematici Helvetici, 53(1):542-571, 1978. Google Scholar
  16. B. Grünbaum and G. C. Shephard. Tilings with congruent tiles. Bulletin of the American Mathematical Society, 3:951-973, 1980. Google Scholar
  17. D. Gusfield. Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology. Cambridge University Press, 1997. Google Scholar
  18. H. Heesch. Aufbau der ebene aus kongruenten bereichen. Nachrichten von der Gesellschaft der Wissenschaften zu Göttingen, 1:115-117, 1935. Google Scholar
  19. H. Heesch and O. Kienzle. Flächenschluss: System der Formen lückenlos aneinanderschliessender Flachteile. Springer, 1963. Google Scholar
  20. D. Hilbert. Mathematical problems. Bulletin of the American Mathematical Society, 8(10):437-479, 1902. Google Scholar
  21. T. I, S. Sugimoto, S. Inenaga, H. Bannai, and M. Takeda. Computing palindromic factorizations and palindromic covers on-line. In A. S. Kulikov, S. O. Kuznetsov, and P. Pevzner, editors, CPM 2014, volume 8486 of LNCS, pages 150-161. Springer, Switzerland, 2014. Google Scholar
  22. K. Keating and A. Vince. Isohedral polyomino tiling of the plane. Discrete and Computational Geometry, 21(4):615-630, 1999. Google Scholar
  23. R. B. Kershner. On paving the plane. The American Mathematical Monthly, 75(8):839-844, 1968. Google Scholar
  24. D. E. Knuth, J. H. Morris, and V. R. Pratt. Fast pattern matching in strings. SIAM Journal on Computing, 6(2):323-350, 1977. Google Scholar
  25. G. K. Manacher. A new linear-time "on-line" algorithms for finding the smallest initial palindrome of a string. Journal of the ACM, 22(3):346-351, 1975. Google Scholar
  26. C. Mann, J. McLoud-Mann, and D. Von Derau. Convex pentagons that admit i-block transitive tilings. Technical report, arXiv, 2015. URL: http://arxiv.org/abs/1510.01186.
  27. W. Matsubara, S. Inenaga, A. Ishino, A. Shinohara, T. Nakamura, and K. Hashimoto. Efficient algorithms to compute compressed longest common substrings and compressed palindromes. Theoretical Computer Science, 410:900-913, 2009. Google Scholar
  28. J. Myers. Polyomino, polyhex, and polyiamond tiling. Online, updated February 2012. URL: http://www.polyomino.org.uk/mathematics/polyform-tiling/.
  29. X. Provençal. Combinatoire des mots, géométrie discrète et pavages. PhD thesis, Université du Québec à Montréal, 2008. Google Scholar
  30. K. Reinhardt. Zur zerlegung der euklidischen räume in kongruente polytope. Sitzungsberichte der Preussischen Akademie der Wissenschaften, pages 150-155, 1928. Google Scholar
  31. G. C. Rhoads. Planar tilings polyominoes, polyhexes, and polyiamonds. Journal of Copmutational and Applied Mathematics, 174:329-353, 2005. Google Scholar
  32. D. Schattschneider. Will it tile? try the Conway criterion! Mathematics Monthly, 53(4):224-233, 1980. Google Scholar
  33. D. Schattschneider. Visions of Symmetry: Notebooks, Periodic Drawings, and Related Work of M. C. Escher. W. H. Freeman and Company, 1990. Google Scholar
  34. J. E. S. Socolar and J. M. Taylor. An aperiodic hexagonal tile. Journal of Combinatorial Theory, Series A, 118(8):2207-2231. Google Scholar
  35. H. A. G. Wijshoff and J. van Leeuwen. Arbitrary versus periodic storage schemes and tessellations of the plane using one type of polyomino. Information and Control, 62:1-25, 1984. Google Scholar
  36. A. Winslow. An optimal algorithm for tiling the plane with a translated polyomino. In 26th International Symposium on Algorithms and Computation (ISAAC), 2015. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact