Convex hulls of polyominoes

Sascha Kurz

Abstract: In this article we prove a conjecture of Bezdek, Braß, and Harborth concerning the maximum volume of the convex hull of any facet-to-facet connected system of $n$ unit hypercubes in $\mathbb{R}^d$ [B]. For $d=2$ we enumerate the extremal polyominoes and determine the set of possible areas of the convex hull for each $n$.

[B] Bezdek, K.; Braß, P.; Harborth, H.: Maximum convex hulls of connected systems of segments and of polyominoes. Beitr. Algebra Geom. {\bf 35}(1) (1994), 37--43. Festschrift on the occasion of the 65th birthday of Otto Krötenheerdt.

Keywords: polyominoes, convex hull, dido-type problem, isoperimetric inequality

Classification (MSC2000): 05B50$^\star$, 05D99, 52C99

Full text of the article:

• Compressed PostScript file (549 kilobytes)
• PDF file (172 kilobytes)