Isohedral Polyomino Tiling of the Plane

Abstract.

A polynomial time algorithm is given for deciding, for a given polyomino P , whether there exists an isohedral tiling of the Euclidean plane by isometric copies of P . The decidability question for general tilings by copies of a single polyomino, or even periodic tilings by copies of a single polyomino, remains open.

Similar content being viewed by others

Deciding multiple tiling by polygons in polynomial time

Article 13 October 2020

Some Open Problems in Polyomino Tilings

Chapter © 2018

Translational Tiling with 8 Polyominoes is Undecidable

Article 29 November 2024

Explore related subjects

Discover the latest articles, books and news in related subjects, suggested using machine learning.

• Combinatorics
• Combinatorial Geometry
• Discrete Mathematics in Computer Science
• Discrete Mathematics
• Polytopes
• Tiling

Author information

Authors and Affiliations

1. Department of Mathematics, University of Florida, Gainesville, FL 32611, USA {keating,vince}@math.ufl.edu, , , , , , US

   K. Keating & A. Vince

Authors

1. K. Keating
   View author publications

   Search author on:PubMed Google Scholar

2. A. Vince
   View author publications

   Search author on:PubMed Google Scholar

Additional information

Received June 23, 1997, and in revised form April 6, 1998.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Keating, K., Vince, A. Isohedral Polyomino Tiling of the Plane . Discrete Comput Geom 21, 615–630 (1999). https://doi.org/10.1007/PL00009442

Download citation

• Issue date: June 1999

• DOI: https://doi.org/10.1007/PL00009442

Keywords

• Polynomial Time
• Time Algorithm
• Polynomial Time Algorithm
• Euclidean Plane
• Decidability Question