Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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)

share|improve this question
    
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 '13 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 '13 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 '13 at 2:15

1 Answer 1

up vote 3 down vote accepted

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.

alt text

share|improve this answer
    
@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 '13 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 '13 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 '13 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 '13 at 6:47
    
@Aaron Meyerowitz In retrospect, my question was atrociously worded. Hopefully I have made it clearer. –  Azure Jan 9 '13 at 6:50

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.