# Minimizing the Perimeter of a polyomino

Imagine I generate some polyomino (http://en.wikipedia.org/wiki/Polyomino) with $N$ unit squares, under the constraint that I want to maximize the number of shared edges between unit squares, or equivalently, minimize the effective surface area of the tiling.

To be a bit more specific, say I give you $N$ unit squares and ask you to do as you wish with them in terms of making a connected polyomino. Once you've finished, I then count how many many of the $4N$ tile edges are shared between two tiles. Your goal is to maximize this count.

How well can we do as a function of $N$? What tiling geometry is optimal - perhaps a rectangle or a square?

We are inspired by this earlier question: (Polyominoes with double contact)

-
Can I pick them or are they given to me? Are they congruent? In general it can be quite hard to decide if a set of polyominos (even if they are congruent) tile a rectangle. By surface area do you mean the smallest rectangle containing all the tiles? Imagine two congruent polyominoes made as follows: fit together four $1 \times 100$ strips to make the outer layer of a square of side $101.$ Now delete the middle $97$ squares from the top. The best way to nest two of these together has only about 6 edges shared. We can achieve $101$ shared edges but that is almost twice the area. –  Aaron Meyerowitz Jan 9 at 1:32
@Aaron Meyerowitz You are given $N$ tiles, and you can make a tiling as you wish with them. You don't have to necessarily make a rectangle, you just need to minimize the number of edges where some $(N+1)th$ tile can be placed. –  Azure Jan 9 at 2:09
@Aaron Meyerowitz I have added to the problem description. Please let me know if you think my question is still underspecified. –  Azure Jan 9 at 2:15

The question is: Consider all the polyominoes $P$ made with $N$ unit squares (cells). Let $E(N)$ be the least perimeter (i.e. number of external edges) among them. What is $E(N)$ and which polyominoes attain it?

Let $k=\lceil \sqrt{N}\rceil$ be the least integer no less than $\sqrt{N}.$ If we could use real numbers for the sides then the least perimeter would be $4\sqrt{N}$ coming from a square. But we will have $E(N)$ an even integer with $E(N) \ge 4\sqrt{N}$.

A short answer is that the lower bound is sharp: $E(N)$ is the least even integer no less than $4\sqrt{N}.$ This means that $E(N)=4k-2$ when $(k-1)^2 \lt N \le (k-1)k$ and $E(N)=4k$ when $(k-1)k \lt N \le k^2$. The tile is unique when $N=k^2,k^2-k-1$ and $k^2-k$ but otherwise there can sometimes be many tiles, especially for $N=k^2+1$ and $N=k(k-1)+1$.

At the end is a tile of area $N=1025$ with perimeter $130$. It arises from appropriately removing $8+10+2+1=21$ cells from the corners of a $31 \times 32$ rectangle. The polyomino and bounding rectangle both have perimeter $130.$ The tiles with perimeter $E(N)$ will be exactly the polyominoes obtained like this: Start with a rectangle of area $ab \ge N$ and perimeter $2a+2b=E(N)$, then appropriately remove $ab-N$ cells from one or more of the corners. In the case of $N=1025$ the bounding rectangle could be $28 \times 37$ with $11$ cells removed or even $27 \times 38$ less one corner cell. Any dimensions $(a,b)=(32-j,33+j)$ with $ab \ge N$ would be possible.

Note that the transition from $E(N)=4k-2$ to $E(N)=4k$ happens at $N=k^2-k+1$ since $4\sqrt{k^2-k}=2\sqrt{4k^2-4k} \lt 4k-2$ but $4\sqrt{k^2-k+1}=2\sqrt{4k^2-4k+4} \gt 4k-2.$ It is clear why the transition form $4k$ to $4k+2$ is at $N=k^2+1.$

The bounding box of a polyomino $P$ is the minimal rectangle which completely contains it (so all 4 sides of the box share an edge with $P$.) If the area of $P$ is $N$ and the bounding box has dimensions $a \times b,$ then clearly, $ab \ge N$. Also $E(N) \ge 2a+2b.$ This is because when we walk around the boundary of $P$, an edge at a time, we go up at least $a$ times, down at least $a$ times, and left and right at least $b$ times each. We will assume that $a \le b$ since we can always rotate $P.$

Depending on $N$ there may be many or few choices of $a,b$ with $N \le ab$ and $2a+2b=E(N)$. Consider again $N=1025=25 \cdot 401.$ If $ab \ge N=1025,$ then $2a+2b \ge 130$ since the minimum over real values is $4\sqrt{1025} \gt 128.$ But we need an even integer. So any of $(a,b)=(32-j,33+j)=(32,33),(31,34),(30,35),(29,36),(28,37),(27,38)$ are possible. $27 \cdot 38=1026$ is big enough but $26 \cdot 39=1014$ would not be. In general, to have area at least $N$ in a box with $2a+2b =4k+2$, we have $(a,b)=(k-j,k+1+j)$ with area $N \le k^2+k-j^2-j$ so $0 \le j \le \frac{-1+\sqrt{4(k^2+k-N)+1}}{2}.$ The calculations for $(a,b)=(k-j,k+j)$ when $E(n)=4k$ are similar.

Even though we could get area exactly $1025$ with a $25 \times 401$ rectangle, the perimeter of $851$ is much worse than $130.$ Now we have arrived at a blue polyomino $P$ with area $1025$ which fits in a $32 \times 33$ bounding box. The $8+10+2+1=21$ black squares are in the bounding box but are not part of $P$.

For any $N$, the polyominoes with area $N$ and perimeter $E(n)$ will those obtained from a bounding rectangle of area $ab \ge N$ with a total of $ab-N$ cells removed in this fashion from some or all the corners.

-
@Aaron Meyerowitz This is very interesting to read. However, my intention was to ask about a polyomino construction and to refer to "sides" as the sides of the squares composing the polyomino. –  Azure Jan 9 at 4:23
$Aaron Meyerowitz For example, a simple cross with tiles at {{0,0},{1,0},{0,1},{-1,0},{0,-1}} would have 12 "free" sides, whereas one could approximate a rectangle with tiles at: {{0,0},{0,1},{1,0},{1,1},{1,2}} that only has 10 "free" sides. – Azure Jan 9 at 4:34 @Aaron Meyerowitz Oh! I meant, I will give you$N\$ copies of unit squares, and you make one polyomino, and try to minimize the number of "free" unit square sides. –  Azure Jan 9 at 6:46
@Aaron Meyerowitz At no point does one try to fit or nest together assemblies of more than one unit square. –  Azure Jan 9 at 6:47
@Aaron Meyerowitz In retrospect, my question was atrociously worded. Hopefully I have made it clearer. –  Azure Jan 9 at 6:50