Tilings and isoperimetrical shapes. II: Hexagonal lattice. (English) Zbl 1042.52018

Let \(\mathcal H\) be the hexagonal lattice. A polyhexe is a finite set (not necessarily connected) of unit hexagons placed on \(\mathcal H\).
The author solves the following problem in \(\mathcal H\): Suppose we are given a positive integer \(n\). What are the polyhexes of perimeter \(n\) with maximal area?
A variant of the isoperimetric inequalities in lattices is considered. A precise description of the polyominoes on the honeycomb lattice which maximize their area for a fixed perimeter is given. From this characterization, the ‘explicit’ values of the smallest perimeter of a polyhexe with a fixed area are given. This characterization is also applied to the problem: Find the minimum density of unit hexagon to be placed on the honeycomb lattice so that to exclude all polyhexes of a fixed area. This problem is solved for some values of the fixed area.
For part I see [S. Gravier and Ch. Payan, ibid., 63–77 (2001; Zbl 1042.52019)].


52C20 Tilings in \(2\) dimensions (aspects of discrete geometry)
52A40 Inequalities and extremum problems involving convexity in convex geometry


Zbl 1042.52019
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] Conway J. H., Sloane N. J. A.: Sphere Packings, Lattices and Groups. Springer-Verlag, 1996. · Zbl 0852.52010
[6] Golomb S. W.: Polyominoes -Puzzles, Patterns, Problems, and Packings. Princeton Science Library, 1994. · Zbl 0831.05020
[7] Gravier S., Payan, C: Tilings and Isoperimetrical Shapes I: Square lattice. Acta Univ. Palacki. Olomuc., Fac. rer. nat., Math. 40 (2001), 57-71. · Zbl 1042.52019
[8] Gravier S., Payan, C: Pentomino Exclusion Problem. Disc. and Comput. Geom., (1999)) · Zbl 0993.05047 · doi:10.1007/s00454-001-0036-9
[9] Melissen H.: Packing and Covering with Circles. PhD Thesis, Proefschrift Universiteit Utrecht, Nederland, 1997. · Zbl 0880.52008
[10] 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.