Polyominoes with the most reflex exterior angles

95 Views Asked by At

What is the polyomino with the largest number $n$ of reflex (i.e., $270^\circ$) exterior angles that can fit in a $L \times L$ grid? How does $n$ scale with $L$?

1

There are 1 best solutions below

0
On BEST ANSWER

This is not an answer but it is at least a lower bound. If $L=3+4n$ where $n \in \Bbb N$, we can make polyominoes of the following structure:

enter image description here

In the examples above $n=0, 1 \text { and } 2$. The number of reflex exterior angles in these structures is given by the formula $$N=8n^2+14n+8 \tag{1}$$

I suspect this cannot be bettered.

EDIT

Some thoughts on an upper bound.

The only cells in a polyomino which can contribute to $N$ are the ones which are singly connected, which contribute $2$ angles, and those which are doubly connected (if the connections are in the form of an L), which contribute $1$ angle. To maximize $N$ we should therefore seek to maximize the number of Singly Connected Cells (SCC in the following).

An SCC needs space around it. In a corner of the grid it only needs $1$ adjacent space. On a side of the grid it needs $2$. In the interior of the grid it needs $5$.

For $L \gt 3$, it therefore seems to me that the SCCs cannot be placed closer to each other than as shown in the figure below:

enter image description here

If such structures were possible, then for L odd we have: $$N = 2 \left(\frac {L+1}{2}\right)^2$$ This then is an upper bound. If we insert $L=3+4n$ in the above formula we get: $$N=8n^2+16n+8$$ Comparing this to equation $(1)$ shows that the lower bound I found is very close to the upper bound.