Tilings and isoperimetrical shapes. I: Square lattice. (English) Zbl 1042.52019

A polyomino is a finite set (not necessary connected) of unit squares centered on the grid \(\mathbb Z^n\). The authors are interested in the following question (Q): Suppose we are given a positive integer \(n\). What are the polyominoes of perimeter \(n\) with maximum area?
This question is related to an isoperimetrical problem: What is the least perimeter of a polyomino of a given area?
The authors solve (Q) for the 2-dimensional case, and propose an application of this result in order to solve a Golomb-type pentomino exclusion problem for the plane: Find the minimum density of unit squares to be placed on the plane to exclude all polyominoes of a fixed area.
The characterization of isoperimetrical shapes allows to solve this problem for some values of the fixed area.


52C20 Tilings in \(2\) dimensions (aspects of discrete geometry)
05B45 Combinatorial aspects of tessellation and tiling problems
05B50 Polyominoes
52A40 Inequalities and extremum problems involving convexity in convex geometry
Full Text: EuDML


[1] Alonso L., Cerf R.: The three dimensional polyominoes of minimal area. Electronic J. of Combin. 3 (1996), 1-39. · Zbl 0885.05056
[2] Bollobás B., Leader I.: Compressions and Isoperimetric Inequalities. J. Combin. Theory Ser. A 56 (1991), 47-62. · Zbl 0731.05043 · doi:10.1016/0097-3165(91)90021-8
[3] Bosch R. A.: A Pentomino Exclusion Problem. Mathematical Programming Newsletter, Optima 60 (december 1998), 3.
[4] Bosch R. A.: Peaceably Coexisting Armies of Queens. Mathematical Programming Newsletter, Optima 62 (June 1999), 3.
[5] Golomb S. W.: Polyominoes - Puzzles, Patterns, Problems, and Packings. Princeton Science Library, 1994. · Zbl 0831.05020
[6] Melissen H.: Packing and Covering with Circles. PhD Thesis, Proefschrift Universiteit Utrecht, Nederland, 1997. · Zbl 0880.52008
[7] Wang D.-L., Wang P.: Extremal configurations on a discrete torus and a generalization of the generalized Macaulay theorem. SIAM J. Appl. Math. 33 (1977), 55-59. · Zbl 0362.05048 · doi:10.1137/0133006
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.