Polyominoes with maximum convex hull
Sascha Kurz · 2004
In the legend of the founding of Carthage Queen Dido purchased the right to get as much land as she could enclose with the skin of an ox. She splitted the skin into thin stripes and tied them together. Using the natural boundary of the sea and by constructing a giant semicircle she enclosed more land than the seller could have ever imagined. Dido-type problems have been treated by many authors, here we consider the maximum volume of a union of unit hypercubes. A d-dimensional polyomino is a facet-to-facet connected system of d-dimensional unit hypercubes. Examples for 2-dimensional polyominoes are the pieces of the computer game Tetris. In 1994 Bezdek, Brass, and Harborth conjectured that the maximum volume of the convex hull of a d-dimensional polyomino consisting of n hypercubes is at most ∑