Section 7.2.2.1: Dancing Links

Exercise 319. [21] After polyominoes, polyiamonds, and polyhexes, the next most popular polyforms are the polyaboloes, originally proposed by S. J. Collins in 1961. These are the shapes obtainable by attaching isoceles right triangles at their edges; for example, there are three diaboloes ${\square, \angle, \square}$. Notice that any $n$-abolo corresponds to a $2n$-abolo, when it has been scaled up by $\sqrt{2}$.

The 14 tetraboloes can be named by using rough resemblances to hexiamonds:

Show that the study of polyaboloes can be reduced to the study of (slightly generalized) polyominoes, just as exercise 318 reduces polyiamonds to polyhexes.

Verified: no
Solve time: 2m45s

---

$$ T(x,y)=(x+y,x-y). $$

The important point is that the image cells must be described with the correct normalization. The transformation $T$ does not send an elementary abolo to a half of a unit square. Instead, it sends an elementary abolo to a half of a square whose side length is $\sqrt2$. These cells form a square-lattice analogue of the original triangular tiling.

Let an abolo be drawn in the usual square grid. Its vertices have integer coordinates, and its edges have directions

$$ (1,0),\qquad (0,1),\qquad (1,1),\qquad (1,-1). $$

Apply the linear transformation

$$ T(x,y)=(x+y,x-y). $$

The determinant is

$$ \det \begin{pmatrix} 1&1\ 1&-1 \end{pmatrix} =-2, $$

so areas are multiplied by $2$. A unit abolo triangle has area $1/2$, hence its image has area $1$.

Consider the elementary triangle with vertices

$$ (0,0),\qquad (1,0),\qquad (0,1). $$

Its image has vertices

$$ (0,0),\qquad (1,1),\qquad (1,-1). $$

This is one half of the square with vertices

$$ (0,0),\qquad (1,1),\qquad (2,0),\qquad (1,-1). $$

The square has area $2$, and the triangular half has area $1$, as required. Every elementary abolo is carried to one of these half-squares, possibly translated or reflected.

The images of the original lattice vertices are precisely the points

$$ (u,v)=(i+j,i-j),\qquad i,j\in\mathbb Z. $$

Equivalently, they are the points of the square lattice rotated by $45^\circ$ and scaled by $\sqrt2$, with the appropriate parity condition. The image of the original square grid therefore becomes a square lattice whose elementary squares are the diamonds

$$ {(u,v): |u-u_0|+|v-v_0|\le 2}. $$

Each elementary abolo is exactly one of the two triangular halves obtained by cutting such a square along one of its diagonals.

Define a generalized polyomino to be a connected union of these elementary half-squares in this rotated square lattice. Ordinary polyominoes consist of whole square cells; here we also allow a square cell to be divided along a diagonal and take either triangular half. These additional triangular cells are the only generalization required.

The transformation $T$ preserves adjacency. If two aboloes share an edge, their images share the corresponding edge of the generalized square-lattice tiling. Conversely, if two generalized cells share an edge, applying $T^{-1}$ gives two elementary abolo triangles sharing the corresponding edge. Therefore a connected polyabolo is carried to a connected generalized polyomino.

The inverse transformation is

$$ T^{-1}(u,v)

\left(\frac{u+v}{2},\frac{u-v}{2}\right). $$

It maps each allowed half-square cell back to an elementary right isosceles triangle of the original abolo tiling. Hence every generalized polyomino of this type corresponds to exactly one polyabolo.

Finally, the transformation is a linear rotation and dilation. It therefore preserves translations, rotations, and reflections of shapes up to the corresponding transformations of the square lattice. Thus equivalence classes of polyaboloes correspond exactly to equivalence classes of these generalized polyominoes.

Consequently, the enumeration and study of polyaboloes can be reduced to the study of slightly generalized polyominoes, in the same way that the triangular tiling of polyiamonds was converted into the hexagonal setting in Exercise $7.2.2.1.318$.

$$ \boxed{\text{Polyaboloes are in one-to-one correspondence with these generalized polyominoes.}} $$