Minimizing the Perimeter of a polyomino - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T21:05:17Z http://mathoverflow.net/feeds/question/118411 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/118411/minimizing-the-perimeter-of-a-polyomino Minimizing the Perimeter of a polyomino Azure 2013-01-09T00:48:18Z 2013-01-09T11:55:08Z <p>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. </p> <p>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. </p> <p>How well can we do as a function of $N$? What tiling geometry is optimal - perhaps a rectangle or a square?</p> <p>We are inspired by this earlier question: (http://mathoverflow.net/questions/117866/polyominos-with-double-contact) </p> http://mathoverflow.net/questions/118411/minimizing-the-perimeter-of-a-polyomino/118416#118416 Answer by Aaron Meyerowitz for Minimizing the Perimeter of a polyomino Aaron Meyerowitz 2013-01-09T03:49:56Z 2013-01-09T11:55:08Z <p>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? </p> <p>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}$. </p> <p>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$. </p> <p>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. </p> <p>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.$ </p> <p>The <em>bounding box</em> 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.$ </p> <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 <code>$N \le k^2+k-j^2-j$</code> 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.</p> <p>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$.</p> <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.</p> <p><img src="https://dl.dropbox.com/u/24793671/tile.png" alt="alt text"></p>