Properties of Minimal-Perimeter Polyominoes

Abstract

A polyomino is a set of connected squares on a grid. In this paper we address the class of polyominoes with minimal perimeter for their area, and we show a bijection between minimal-perimeter polyominoes of certain areas.

Work on this paper by both authors has been supported in part by ISF Grant 575/15.

1 Introduction

A polyomino is an edge-connected set of cells on the square lattice. The area of a polyomino is the number of cells it contains. The problem of counting polyominoes dates back to the 1950s when it was studied in parallel in the fields of combinatorics [8] and statistical physics [6]. Let A(n) denote the number of polyominoes of area n. A general formula for A(n) is still unknown. Klarner [10] showed the existence of the growth rate of A(n), denoting it by $\lambda := \lim _{n\rightarrow \infty }\root n \of {A(n)}$. The exact value of $\lambda$ is also unknown yet, and its best estimate, 4.06, is by Jensen [9]. The current best lower and upper bounds on $\lambda$ are 4.0025 [3] and 4.6496 [11], respectively. Several works provide enumeration by area of special classes of polyominoes, such as column-convex [7], convex [5], and directed [4] polyominoes.

The perimeter of a polyomino is the set of empty cells that are adjacent to at least one polyomino cell, where, as above, two cells are adjacent if thy share a common edge of the lattice. Although less explored than the area, some works studied the perimeter of polyominoes. Asinowski et al. [2] showed that $2n+2$ is the maximum possible perimeter size for a polyomino of area n, and provided a few formulae for the numbers of polyominoes with area n and perimeter $2n+2-k$, for some small values of k. In this paper, we shed some light on the opposite aspect of this type of polyominoes, namely, polyominoes with the minimal perimeter for their area. Closely related works are by Altshuler et al. [1] and by Sieben [13], both providing a formula for the maximum area of a polyomino with a certain perimeter size. Sieben [13] also gave a formula for the minimum perimeter of a polyomino of area n. Both works also characterized all the polyominoes that have the maximum area for a given perimeter size. Ranjan and Zubair [12] showed a similar result about the minimum perimeter of a directed graph on an infinite grid. In this paper, we study the number of polyominoes which have the minimum perimeter for their area. We define the operation of inflating a polyomino as the extension of a polyomino by all its perimeter cells, and show the following: (1) All minimal-perimeter polyominoes of some area n are inflated into polyominoes of the same area $n'$. (Polyominoes of the same area, which are not minimal perimeter, may be inflated into polyominoes of different areas.) (2) The inflation operation induces a bijection between the sets of minimal-perimeter polyominoes of area n and the set of minimal-perimeter polyominoes of area $n'$.

In Sect. 2 we define the notions used throughout this paper. In Sect. 3 we discuss some properties of polyominoes through an analysis of the patterns that may appear in the perimeter. Section 4 is where we reach our main result, proving that the inflating operation induces a bijection between sets of minimal-perimeter polyominoes. We end in Sect. 5 with some concluding remarks.

2 Preliminaries

Let $Q$ be a polyomino, and let $\mathcal {P}(Q)$ be the perimeter of $Q$. Define $\mathcal {B}(Q)$, the border of $Q$, to be the set of cells of $Q$ that have at least one empty neighboring cell. Given a polyomino $Q$, its inflated polyomino, $I(Q)$, is defined as $I(Q) = Q\cup \mathcal {P}(Q)$. Notice that the border of $I(Q)$ is a subset of the perimeter of $Q$. Analogously, the deflated polyomino, $D(Q)$, is defined as $D(Q) = Q\setminus \mathcal {B}(Q)$, which is obtained by “shaving” the outer layer, i.e., the border cells from the polyomino. Notice that the perimeter of $D(Q)$ is a subset of the border of $Q$. Also note that $D(Q)$ is not necessarily a valid polyomino since the removal of the border of $Q$ may break it into disconnected pieces. Figure 1 demonstrates all the above definitions.

Fig. 1.

A polyomino $Q$, its inflated polyomino, and its deflated polyomino. The gray cells are the polyomino cells, while the white cells are the perimeter. Border cells are marked with crosses.

Following the notation of Sieben [13], we denote by $\epsilon (n)$ the minimum size of the perimeter of all polyominoes of area n. Sieben showed that $\epsilon (n) = \left\lceil 2+\sqrt{8n-4} \right\rceil$. A polyomino $Q$ of area n will be called a minimal-perimeter polyomino if $\left| \mathcal {P}(Q)\right| = \epsilon (n)$.

3 Border, Perimeter, and Excess

In this section, we express the size of the perimeter of a polyomino, $\left| \mathcal {P}(Q)\right|$, as a function of the border size, $\left| \mathcal {B}(Q)\right|$, and the number of excess cells as defined below. The excess of a perimeter cell [2] is defined as the number of polyomino cells that are adjacent to it minus one, and the total excess of a polyomino $Q$, $e_P$, is defined as the sum of excess over all the cells of the perimeter of $Q$. Similarly, the excess of a border cell is defined as the number of perimeter cells adjacent to it minus one, and the border excess, denoted by $e_B$, is defined as the sum of excess over all the border cells. Let $\pi = \left| \mathcal {P}(Q)\right|$ and $\beta =\left| \mathcal {B}(Q)\right|$.

Observation 1

The following holds for any polyomino: $\pi + e_P = \beta + e_B$. Equivalently,

$$\begin{aligned} \pi = \beta + e_B - e_P. \end{aligned}$$

(1)

Fig. 2.

All possible patterns of excess cells. The gray cells are polyomino cells, while the white cells are perimeter cells. Patterns (a–d) exhibit excess border cells and their surrounding perimeter cells, while Patterns (w–z) exhibit excess perimeter cells and their surrounding polyomino cells.

Fig. 3.

A sample polyomino with marked patterns.

Equation (1) holds since both $\pi + e_P$ and $\beta + e_B$ are equal to the total length of the polygons forming the boundary of the polyomino. This quantity can be calculated either by summing up over the perimeter cells, where each cell contributes 1 plus its excess for a total of $\pi +e_P$, or by summing up over the border cells for a total of $\beta +e_B$. Figure 2 shows all possible patterns of border and perimeter excess cells, while Fig. 3 shows a sample polyomino with some cells tagged with the corresponding patterns.

Let $\#\square$ be the number of excess cells of a certain type in a polyomino as classified in the figure, where ‘$\square$’ is one of the symbols a–d or w–z, as in Fig. 2. Counting $e_P$ and $e_B$ as functions of the different patterns of excess cells, we see that $e_B = \#a + 2\#b + 3\#c + \#d$ and $e_P = \#w + 2\#x + 3\#y + \#z.$ Substituting $e_B$ and $e_P$ in Eq. (1), we obtain

$$ \pi = \beta + \#a + 2\#b+3\#c + \#d - \#w - 2\#x-3\#y - \#z. $$

Since Pattern (c) is a singleton cell, we can ignore it in the general formula. Thus, we have

$$ \pi = \beta + \#a + 2\#b + \#d - \#w - 2\#x-3\#y - \#z. $$

3.1 Properties of Minimal-Perimeter Polyominoes

We now discuss the relation between the perimeter and the border of minimal-perimeter polyominoes.

Lemma 1

Any minimal-perimeter polyomino is simply connected (that is, it does not contain holes).

Proof

The sequence $\epsilon (n)$ is monotone increasing in the wide sense¹ [13]. Assume that there exists a minimal-perimeter polyomino $Q$ with a hole. Consider the polyomino $Q'$ that is obtained by filling this hole. The area of $Q'$ is clearly larger than the area of $Q$, and its perimeter size is smaller since we eliminated the perimeter cells inside the hole and did not introduce new perimeter cells. This is a contradiction to $\epsilon (n)$ being monotone increasing.    $\square$

Lemma 2

For a simply connected polyomino, we have $\#a\,+\,2\#b\,-\,\#w\,-\,2\#x\,=\,4.$

Proof

The boundary of a polyomino without holes is a simple polygon, thus, the sum of its internal angles is $(180(v-2))^\circ$, where v is the complexity of the polygon. Notice that Pattern (a) (resp., (b)) adds one (resp., two) $90^\circ$-vertex to the polygon. Similarly, Pattern (w) (resp. (x)) adds one (resp., two) $270^\circ$-vertex. All other patterns do not involve vertices. Let $L\,=\,\#a\,+\,2\#b$ and $R\,=\,\#w\,+\,2\#x$. Then, the sum of angles of the boundary polygon implies that $L \cdot 90^\circ + R \cdot 270^\circ = (L+R-2) \cdot 180^\circ$, that is, $L-R = 4$. The claim follows.    $\square$

Theorem 2

(Stepping Theorem) For a minimal-perimeter polyomino (except the singleton cell), we have that $\pi =\beta +4.$

Proof

Lemma 2 tells us that $\pi =\beta +4+\#d-\#z$. We will show that any minimal-perimeter polyomino contains neither Pattern (d) nor Pattern (z).

Let $Q$ be a minimal-perimeter polyomino. For the sake of contradiction, assume first that there is a cell $f \in \mathcal {P}(Q)$ as part of Pattern (z). Assume w.l.o.g. that the two adjacent polyomino cells are to the left and to the right of f. These two cells must be connected, thus, the area below (or above) f must be bounded by polyomino cells. Let, then, $Q'$ be the polyomino with the area below f, and the cell f itself, filled with polyomino cells. The cell directly above f becomes a perimeter cell, the cell f ceases to be a perimeter cell, and at least one perimeter cell in the area filled below f is eliminated, thus, $\left| \mathcal {P}(Q')\right| < \left| \mathcal {P}(Q)\right|$ and $\left| Q'\right| > \left| Q\right|$, which is a contradiction to the sequence $\epsilon (n)$ being monotone increasing. Therefore, the polyomino $Q$ does not contain perimeter cells that fit Pattern (z). Figures 4(a, b)

Fig. 4.

Examples for the first and second parts of the proof of Theorem 2.

demonstrate this argument.

Now assume for contradiction that $Q$ contains a cell f, forming Pattern (d). Let $Q'$ be the polyomino obtained from $Q$ by removing f and then “pushing” together the two cells adjacent to f. This is always possible since $Q$ is of minimal perimeter, hence, by Lemma 1, it is simply connected, and thus, removing f breaks $Q$ into two separate polyominoes. Any two separated polyominoes can be shifted by one cell without colliding, thus, the transformation described above is valid. The area of $Q'$ is one less than the area of $Q$, and the perimeter of $Q'$ is smaller by at least two than the perimeter of $Q$, since the perimeter cells below and above f cease to be part of the perimeter, and connecting the two parts does not create new perimeter cells. From the formula of $\epsilon (n)$ we know that $\epsilon (n)-\epsilon (n-1) \le 1$ for $n \ge 3$, but $\left| Q\right| - \left| Q'\right| = 1$ and $\left| \mathcal {P}(Q)\right| - \left| \mathcal {P}(Q')\right| = 2$, hence, $Q$ is not a minimal-perimeter polyomino, which contradicts our assumption. Thus, there are no cells in $Q$ that fit Pattern (d). Figures 4(c, d) demonstrate this argument. This completes the proof.    $\square$

4 Inflating a Minimal-Perimeter Polyomino

In this section we reach our main results. First, we show that inflating a minimal-perimeter polyomino results in a minimal-perimeter polyomino as well. Second, we show that if any minimal-perimeter polyomino of a certain area $n'$ is created by inflating a minimal-perimeter polyomino of area n, then all minimal-perimeter polyominoes of area $n'$ are created by inflating polyominoes of area n. Furthermore, inflating different minimal-perimeter polyominoes of area n results in different minimal-perimeter polyominoes of area $n'$, and so, this operation induces a bijection between the two sets.

Lemma 3

If $Q$ is a minimal-perimeter polyomino, then $I(Q)$ is simply connected.

Proof

Let $Q$ be a minimal-perimeter polyomino, and assume that $I(Q)$ is not simply connected, i.e., it contains a hole. Let $Q'$ be the polyomino obtained by filling the holes of $Q$ by polyomino cells. Notice that this operation only eliminates border cells of $I(Q)$, and does not create any new border cells, thus, $\mathcal {B}(Q') \subset \mathcal {B}(I(Q))$. Let us now compare the polyomino $D(Q')$ to the original polyomino $Q$. On the one hand, by the way $Q'$ is constructed, $\left| Q'\right| > \left| I(Q)\right|$, and since $\mathcal {B}(Q') \subset \mathcal {B}(I(Q))$, we have that $\left| D(Q')\right| > \left| D(I(Q))\right|$. Using the fact that the border of an inflated polyomino is a subset of the perimeter of the original polyomino, we have that $\mathcal {B}(I(Q)) \subset \mathcal {P}(Q)$, thus, $\left| D(I(Q))\right| \ge \left| Q\right|$, and, hence, $\left| D(Q')\right| > \left| Q\right|$. On the other hand, we have that $\left| \mathcal {P}(D(Q'))\right| \le \left| \mathcal {B}(Q')\right|$ since the perimeter of a deflated polyomino is a subset of the border of the original polyomino, and we have already established that $\left| \mathcal {B}(Q')\right| < \left| \mathcal {B}(I(Q))\right| \le \left| \mathcal {P}(Q)\right|$, thus, $\left| \mathcal {P}(D(Q'))\right| < \left| \mathcal {P}(Q)\right|$. But we have shown above that $\left| D(Q')\right| > \left| Q\right|$, which is in contradiction to $\epsilon (n)$ being an increasing sequence.    $\square$

Lemma 4

If $Q$ is a minimal-perimeter polyomino, then $\left| \mathcal {P}(I(Q))\right| \le \left| \mathcal {P}(Q)\right| \,+\,4$.

Proof

By Lemma 3 we have that $I(Q)$ is simply connected. Thus, by Lemma 2, we have that $\left| \mathcal {P}(I(Q))\right| = \left| \mathcal {B}(I(Q))\right| + 4 + \#d - \#z$. Since $\left| \mathcal {B}(I(Q))\right| \le \left| \mathcal {P}(Q)\right|$, all that remains to show is that Pattern (d) does not occur in $I(Q)$. Assume to the contrary that there is a cell f forming Pattern (d) in $I(Q)$. This cell is a “bridge” in the polyomino. Since $I(Q)$ is simply connected, removing f will break it into exactly two pieces, denoted by $Q_1$ and $Q_2$. Both $Q_1$ and $Q_2$ must contain cells of the original $Q$ since any cell in $I(Q)$ either belongs to $Q$ or is adjacent to a cell of $Q$. However, this implies that $Q$ is not connected, which is a contradiction. Hence, $Q$ cannot contain a pattern of type (d), as required.    $\square$

Theorem 3

(Inheritance Theorem) If $Q$ is a minimal-perimeter polyomino, then $I(Q)$ is a minimal-perimeter polyomino as well.

Proof

Let $Q$ be a minimal-perimeter polyomino. Assume to the contrary that $I(Q)$ is not a minimal-perimeter polyomino, i.e., there exists a polyomino $Q'$ with the same area as $I(Q)$, such that $\left| \mathcal {P}(Q')\right| < \left| \mathcal {P}(I(Q))\right|$. From Lemma 4 we know that $\left| \mathcal {P}(I(Q))\right| \le \left| \mathcal {P}(Q)\right| + 4$, thus, the perimeter of $Q'$ is at most $\left| \mathcal {P}(Q)\right| +3$, and since $Q'$ is a minimal-perimeter polyomino, we know by Theorem 2 that the size of its border is at most $\left| \mathcal {P}(Q)\right| -1$. Consider now the polyomino $D(Q')$. The area of $Q'$ is $\left| Q\right| +\left| \mathcal {P}(Q)\right|$, thus, the size of $D(Q')$ is at least $\left| Q\right| +1$, and its perimeter size is at most $\epsilon (n)-1$ (since the perimeter of $D(Q')$ is a subset of the border of $Q'$). This is a contradiction to the fact that the sequence $\epsilon (n)$ is monotone increasing. Hence, the polyomino $Q'$ cannot exist, and $I(Q)$ is a minimal-perimeter polyomino. Figure 5 demonstrates this theorem. It shows a minimal-perimeter polyomino $Q$ of area 6 and the two minimal-perimeter polyominoes of areas 15 and 28 obtained by inflating $Q$ twice.    $\square$

Fig. 5.

A demonstration of Theorem 3.

Corollary 1

The minimum perimeter size of a polyomino of area $n+k\epsilon (n)+2k(k-1)$ (for $n \ne 1$ and any $k \in \mathbb {N}$) is $\epsilon (n)+4k$.

Proof

The claim follows from repeatedly applying Theorem 3 to a minimal-perimeter polyomino of area n. Indeed, inflating once a minimal-perimeter polyomino $Q$ of area n increases the area by $\epsilon (n)$, and the new border size is $\epsilon (n)$. Thus, by Theorem 2, the perimeter size increases by 4, becoming $\epsilon (n)+4$. Inflating the new polyomino again increases the area by $\epsilon (n)+4$, forming yet a new polyomino with perimeter $\epsilon (n)+8$. Thus, by induction, the kth inflation of the polyomino increases the area by $\epsilon (n)+4(k-1)$, forming a polyomino with perimeter size $\epsilon (n)+4k$. As to the area, summing up the contributions in all steps yields $\sum _{i=1}^k (\epsilon (n)+4(i-1)) = k\epsilon (n)+2k(k-1)$, implying the claim.    $\square$

Lemma 5

Let $Q$ be a minimal-perimeter polyomino of area $n\,+\,\epsilon (n)$ (for $n \ge 3$). Then, $D(Q)$ is a valid (connected) polyomino.

Proof

Assume to the contrary that $D(Q)$ is not connected and that it is composed of at least two parts. Assume first that $D(Q)$ is composed of exactly two parts, $Q_1$ and $Q_2$. Define the joint perimeter of the two parts, $\mathcal {P}(Q_1,Q_2)$, to be $\mathcal {P}(Q_1) \cup \mathcal {P}(Q_2)$. Since $Q$ is a minimal-perimeter polyomino of area $n+\epsilon (n)$, we know that its perimeter size is $\epsilon (n)+4$ and its border size is $\epsilon (n)$, by Corollary 1 and Theorem 2, respectively. Thus, the size of $D(Q)$ is exactly n regardless of whether or not $D(Q)$ is connected. Since $Q_1$ and $Q_2$ are the result of deflating $Q$, the polyomino $Q$ must have an (either horizontal, vertical, or diagonal) “bridge” of border cells which disappeared in the deflation. The width of the bridge is at most 2, thus, $\left| \mathcal {P}(Q_1) \cap \mathcal {P}(Q_2)\right| \le 2$. Hence, $\left| \mathcal {P}(Q_1)\right| + \left| \mathcal {P}(Q_2)\right| - 2 \le \left| \mathcal {P}(Q_1,Q_2)\right|$. Since $\mathcal {P}(Q_1,Q_2)$ is a subset of $\mathcal {B}(Q)$, we have that $\left| \mathcal {P}(Q_1,Q_2)\right| \le \epsilon (n)$. Therefore,

$$\begin{aligned} \epsilon (\left| Q_1\right| ) + \epsilon (\left| Q_2\right| ) - 2 \le \epsilon (n). \end{aligned}$$

(2)

Fig. 6.

Values of $\epsilon (n)$.

Recall that $\left| Q_1\right| + \left| Q_2\right| = n$. It is easy to observe that $\epsilon (\left| Q_1\right| )+\epsilon (\left| Q_2\right| )$ is minimized when $\left| Q_1\right| =1$ and $\left| Q_2\right| = n-1$ (or vice versa). Had the function $\epsilon (n)$ (shown in Fig. 6) been $2+\sqrt{8n-4}$ (without rounding up), this would be obvious. But since $\epsilon (n) = \left\lceil 2+\sqrt{8n-4} \right\rceil$, it is a step function (with an infinite number of intervals), where the gap between all successive steps is exactly 1, except the gap between the two leftmost steps which is 2. This guarantees that despite the rounding, the minimum of $\epsilon (\left| Q_1\right| )\,+\,\epsilon (\left| Q_2\right| )$ occurs as claimed. Substituting this into Eq. (2), and using the fact that $\epsilon (1)=4$, we see that $\epsilon (n-1) + 2 \le \epsilon (n)$. However, we know [13] that $\epsilon (n) - \epsilon (n-1) \le 1$ for $n\ge 3$, which is a contradiction. Thus, $D(Q)$ cannot split into two parts unless it splits into two singleton cells, which is indeed the case for a minimal-perimeter polyomino of size 8.

The same method can be used to show that $D(Q)$ cannot be composed of more then two parts. Note that this proof does not hold for polyominoes of area which is not of the form $n+\epsilon (n)$, but it suffices for the proof of Theorem 4 below.    $\square$

Lemma 6

Let $Q_1,Q_2$ be two different minimal-perimeter polyominoes. Then, regardless of whether or not $Q_1,Q_2$ have the same area, the polyominoes $I(Q_1)$ and $I(Q_2)$ are different as well.

Proof

Assume to the contrary that $Q= I(Q_1) = I(Q_2)$. By definition, this means that $Q= Q_1 \cup \mathcal {P}(Q_1) = Q_2 \cup \mathcal {P}(Q_2)$. Furthermore, since $Q_1 \ne Q_2$, and since a cell can belong to either a polyomino or to its perimeter, but not to both, it must be that $\mathcal {P}(Q_1) \ne \mathcal {P}(Q_2)$. The border of $Q$ is a subset of both $\mathcal {P}(Q_1)$ and $\mathcal {P}(Q_2)$, that is, $\mathcal {B}(Q) \subset \mathcal {P}(Q_1) \cap \mathcal {P}(Q_2)$. Since $\mathcal {P}(Q_1) \ne \mathcal {P}(Q_2)$, we have that either $\left| \mathcal {B}(Q)\right| < \left| \mathcal {P}(Q_1)\right|$ or $\left| \mathcal {B}(Q)\right| < \left| \mathcal {P}(Q_2)\right|$; assume w.l.o.g. the former case. Now consider the polyomino $D(Q)$. Its area is $\left| Q\right| -\left| \mathcal {B}(Q)\right|$. The area of $Q$ is $\left| Q_1\right| +\left| \mathcal {P}(Q_1)\right|$, thus, $\left| D(Q)\right| > \left| Q_1\right|$, and since the perimeter of $D(Q)$ is a subset of the border of $Q$, we conclude that $\left| \mathcal {P}(D(Q))\right| < \left| \mathcal {P}(Q_1)\right|$. However, $Q_1$ is a minimal-perimeter polyomino, which is a contradiction to $\epsilon (n)$ being monotone increasing.    $\square$

Theorem 4

(Chain Theorem) Let $M_n$ be the set of minimal-perimeter polyominoes of area n. Then, for $n \ge 3$, we have that $\left| M_n\right| = \left| M_{n+\epsilon (n)}\right|$.

Proof

By Theorem 3, if $Q\in M_n$, then $I(Q) \in M_{n+\epsilon (n)}$, and hence, by Lemma 6, we have that $\left| M_n\right| \le \left| M_{n+\epsilon (n)}\right|$. Let us now show the opposite relation, namely, that $\left| M_n\right| \ge \left| M_{n+\epsilon (n)}\right|$. The combination of the two relations will imply the claim.

Let $I(M_n) = \left\{ I(Q) \mid Q\in M_n\right\}$. For a polyomino $Q\in M_{n+\epsilon (n)}$, our goal is to show that $Q\in I(M_n)$. Since $Q\in M_{n+\epsilon (n)}$, we have by Corollary 1 that $\left| \mathcal {P}(Q)\right| = \epsilon (n)+4$. Moreover, by Theorem 2, we have that $\left| \mathcal {B}(Q)\right| = \epsilon (n)$, thus, $\left| D(Q)\right| = n$ and $\left| \mathcal {P}(D(Q))\right| \ge \epsilon (n)$. Since the perimeter of $D(Q)$ is a subset of the border of $Q$, and $\left| \mathcal {B}(Q)\right| = \epsilon (n)$, we conclude that the perimeter of $D(Q)$ and the border of $Q$ are the same set of cells. Thus, $I(D(Q)) = Q$. Since $\left| \mathcal {P}(D(Q))\right| = \epsilon (n)$, we have that $D(Q)$ is a minimal-perimeter polyomino, thus, $Q\in I(M_n)$ as required. Hence, $M_{n+\epsilon (n)} \subseteq I(M_n)$, implying that $\left| M_{n+\epsilon (n)}\right| \le \left| I(M_n)\right| = \left| M_n\right|$.

Fig. 7.

A demonstration of Theorem 4.

Figure 7 shows, for example, all minimal-perimeter polyominoes of area 7. When they are inflated, they become the entire set of minimal-perimeter polyominoes of area 17.    $\square$

Corollary 2

For $n \ge 3$ and any $k \in \mathbb {N}$, we have that $\left| M_n\right| = \left| M_{n+k\epsilon (n)+2k(k-1)}\right|$.

Proof

The claim follows from applying Theorem 4 repeatedly on $M_n$.    $\square$

5 Conclusion

We have shown that inflating a set of minimal-perimeter polyominoes of a certain area creates a new set, of the same cardinality, of minimal-perimeter polyominoes of some other area. This creates chains of sets of minimal-perimeter polyominoes of the same area.

In the future, we would like to characterize the roots of these chains and to determine how many minimal-perimeter polyominoes the sets of each chain contains. One may take an algorithmic approach in order to calculate the number of minimal-perimeter polyominoes of a certain area. It seems to be feasible to calculate efficiently the number of minimal-perimeter polyominoes of some area using dynamic programing, utilizing the constraints induced by the special geometric structures of such polyominoes.