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

DOI10.4230/LIPICS.SOCG.2016.50MaRDI QIDQ3132886zbMATH OpenOpenAlexFDO

Authors Stefan Langerman, Andrew Winslow

Publication date 30 January 2018

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

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)

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.

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

Cited in

(10)

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

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)