Isohedral Polyomino Tiling of the Plane

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. Received June 23, 1997, and in revised form April 6, 1998.