๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Tiling Rectangles and Half Strips with Congruent Polyominoes

โœ Scribed by Michael Reid

Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
322 KB
Volume
80
Category
Article
ISSN
0097-3165

No coin nor oath required. For personal study only.

โœฆ Synopsis

In the second edition of Golomb's classic ``Polyominoes'' [9], several infinite families of rectifiable polyominoes are given, but only nine sporadic examples are known. Curiously, two of these sporadic examples are related by a 2_1 affine transformation (Fig. 1).

This led us to consider the images of other sporadic rectifiable polyominoes under this transformation. The examples in Fig. 2 were noticed because they have easy tilings of infinite half strips (Fig. 3), but neither has an obvious rectangular tiling.

๐Ÿ“œ SIMILAR VOLUMES

Packing Rectangles with Congruent Polyom
Packing Rectangles with Congruent Polyominoes
โœ William Rex Marshall ๐Ÿ“‚ Article ๐Ÿ“… 1997 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 787 KB

Golomb has covered the main previous results of tiling a rectangle with congruent polyominoes in the revised edition of ``Polyominoes' ' (1994). This article attempts to summarise recent discoveries of many new examples of polyominoes which pack rectangles.

Tiling a Square with Eight Congruent Pol
Tiling a Square with Eight Congruent Polyominoes
โœ Michael Reid ๐Ÿ“‚ Article ๐Ÿ“… 1998 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 76 KB

The problem of finding polyominoes that tile rectangles has attracted a lot of attention; see [1] for an overview, and [2, 3] for more recent results. Several general families of such polyominoes are known, but sporadic examples seem to be scarce. Marshall [2, Fig. 9] gives a polyomino of rectangula

Efficient Approximation Algorithms for T
Efficient Approximation Algorithms for Tiling and Packing Problems with Rectangles
โœ Piotr Berman; Bhaskar DasGupta; S Muthukrishnan; Suneeta Ramaswami ๐Ÿ“‚ Article ๐Ÿ“… 2001 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 202 KB

We provide improved approximation algorithms for several rectangle tiling and packing problems (RTILE, DRTILE, and d-RPACK) studied in the literature. Most of our algorithms are highly efficient since their running times are near-linear in the sparse input size rather than in the domain size. In add