An optimal algorithm for tiling the plane with a translated polyomino

DOI10.1007/978-3-662-48971-0_1MaRDI QIDQ3459844zbMATH OpenOpenAlexFDO

Authors Andrew Winslow

Publication date 11 January 2016

Published in Algorithms and Computation (Search for Journal in Brave)

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

Mathematics Subject Classification ID

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

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 such tilings that are also regular, and we prove that at most $Theta(n)$ such tilings exist.

Recommendations

• An algorithm for deciding if a polyomino tiles the plane
• A Quasilinear-Time Algorithm for Tiling the Plane Isohedrally with a Polyomino
• On translating one polyomino to tile the plane
• Isohedral polyomino tiling of the plane
• On the tiling by translation problem

Cited in

(24)

• On the tiling by translation problem
• On translating one polyomino to tile the plane
• Isohedral polyomino tiling of the plane
• Tiling of planar figures without gaps by dominos: graphical foundations of Thurston if algorithm, parallelization uniqueness and decomposion
• Deciding multiple tiling by polygons in polynomial time
• Tiling a polygon with parallelograms
• Generation of Polyiamonds for p6 Tiling by the Reverse Search
• A Quasilinear-Time Algorithm for Tiling the Plane Isohedrally with a Polyomino
• A new mathematical model for tiling finite regions of the plane with polyominoes
• Minimum boundary touching tilings of polyominoes
• Optimal Partial Tiling of Manhattan Polyominoes
• scientific article; zbMATH DE number 3906514 (Why is no real title available?)
• Arbitrary versus periodic storage schemes and tessellations of the plane using one type of polyomino
• scientific article; zbMATH DE number 806590 (Why is no real title available?)
• scientific article; zbMATH DE number 1445361 (Why is no real title available?)
• scientific article; zbMATH DE number 7278010 (Why is no real title available?)
• On the number of p4-tilings by an n-omino
• An Optimal Algorithm for Detecting Pseudo-squares
• An algorithm for deciding if a polyomino tiles the plane
• Polyomino convolutions and tiling problems
• Tiling the plane with a set of ten polyominoes
• Undecidability of translational tiling of the 4-dimensional space with a set of 4 polyhypercubes
• Undecidability of translational tiling of the 3-dimensional space with a set of 6 polycubes
• Translational tiling with 8 polyominoes is undecidable

This page was built for publication: An optimal algorithm for tiling the plane with a translated polyomino

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