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

DOI10.4230/LIPICS.SOCG.2016.50zbMATH Open1387.68266arXiv1507.02762OpenAlexW2964109259MaRDI QIDQ3132886FDOQ3132886

Authors: Stefan Langerman, Andrew Winslow 

Publication date: 30 January 2018

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(nlo{g}^{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, Provenc{c}al, F'{e}dou, and the second author.

Full work available at URL: https://arxiv.org/abs/1507.02762

Recommendations

• An optimal algorithm for tiling the plane with a translated polyomino
• Deciding multiple tiling by polygons in polynomial time
• An algorithm for deciding if a polyomino tiles the plane
• Tiling with Squares and Packing Dominos in Polynomial Time
• Isohedral polyomino tiling of the plane
• Tiling the Plane with a Fixed Number of Polyominoes
• A New Approximation Algorithm for Multidimensional Rectangle Tiling
• Tessellating polyominos in the plane

zbMATH Keywords

polyominoplane tilingisohedralboundary word

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Polyominoes (05B50) Tilings in (2) dimensions (aspects of discrete geometry) (52C20)

Cited In (10)

• On the number of isohedral polyominoes
• An algorithm for deciding if a polyomino tiles the plane
• Title not available (Why is that?)
• Title not available (Why is that?)
• Tiling of planar figures without gaps by dominos: graphical foundations of Thurston if algorithm, parallelization uniqueness and decomposion
• Title not available (Why is that?)
• On the number of p4-tilings by an \(n\)-omino
• Code for polyomino and computer search of isospectral polyominoes
• An optimal algorithm for tiling the plane with a translated polyomino
• Polyominoes and polyiamonds as fundamental domains for isohedral tilings of crystal class \(D_2\)

This page was built for publication: A Quasilinear-Time Algorithm for Tiling the Plane Isohedrally with a Polyomino

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3132886)