Tiling with Three Polygons Is Undecidable

The relevant angles are $\alpha =\frac{\pi }{2}-2\epsilon =\frac{3\pi }{8}$, $\beta =\frac{\pi }{2}-\epsilon =\frac{7\pi }{16}$, $2\alpha =\frac{3\pi }{4}$, $2\beta =\frac{7\pi }{8}$, and $\alpha +\beta =\frac{13\pi }{16}$, which all have a doubly even denominator (divisible by $4$). Because $n$ is odd, these numbers cannot be equal to $\frac{i\pi }{2n}$ for any integer $i$, so none of these angles are clean. $◀$

Table 1 lists the angles used by each polygon, colored to indicate which are clean. Angles $\alpha ,\beta$ are all a bit less than ${90}^{\circ }$, so a sum of two of them is a bit less than ${180}^{\circ }$, and a sum of three of them is a bit less than ${270}^{\circ }$. More precisely:

The staple has convex vertices just of angle $\beta$ and one reflex vertex of defect $2\alpha$. In any tiling of staples, every reflex vertex must have its defect $2\alpha$ filled by some convex angles. But $2\alpha =\frac{3}{4}\pi$, so by Lemma 3.2, it must be filled by exactly two convex angles. But $2\beta =\frac{7}{8}\pi >2\alpha$, so two of the convex angles do not fit. Thus it is impossible to exactly fill the deficit. $◀$

By Lemma 3.3, any tiling with staples and shurikens has a shuriken. Any shuriken has a reflex anticorner of defect $\pi (1-\frac{1}{2n})$, which is clean and less than $\pi$. This defect must be filled by some convex angles, of which we have three: $\alpha ,\beta ,\frac{\pi }{n}$. By Lemma 3.2, this defect can be filled by at most two angles $\in \{\alpha ,\beta \}$. But by Property 1, summing one or two of these angles is not clean, while the remaining convex angle $\frac{\pi }{n}$ and the target sum $\pi (1-\frac{1}{2n})$ are. Thus we cannot use any angles $\in \{\alpha ,\beta \}$ to fill the deficit, leaving only the convex angle $\frac{\pi }{n}$. But $\frac{\pi }{n}$ is an even multiple of $\frac{\pi }{2n}$, while the target sum is an odd multiple of $\frac{\pi }{2n}$. Thus it is impossible to exactly fill the deficit. $◀$

By Lemma 3.4, any tiling with staples, shurikens, and wheels has a wheel. Any wheel has a convex corner of angle $\pi (1-\frac{1}{2n})$, which has a deficit of $\pi (1+\frac{1}{2n})$, which is clean. We claim that this deficit can be filled in exactly two ways: one reflex anticorner of a shuriken of deficit $\pi (1-\frac{1}{2n})$, or one convex tip vertex of a shuriken of angle $\frac{\pi }{n}$ and one convex corner of a wheel of angle $\pi (1-\frac{1}{2n})$.

Because the target deficit is $>\pi$, we need to consider both convex and reflex angles as well as flat edges (of angle $\pi$) for possible fillings. First consider the unclean angles starting with reflex angles of deficit $\alpha ,\beta ,2\alpha ,2\beta$. But for any $n\ge 5$. Thus none of the unclean reflex angles can be used to fill the deficit. The only remaining reflex angle that can fill the deficit is a shuriken anticorner of deficit $\pi (1-\frac{1}{2n})$, and if we use that angle, we are done.

Next consider the unclean convex angles $\alpha$ and $\beta$. Because for any $n\ge 5$, by Lemma 3.2 this deficit can be filled by at most two angles $\in \{\alpha ,\beta \}$. But by Lemma 1, summing one or two of these angles is not clean, while the remaining convex angles $\frac{\pi }{n},\pi (1-\frac{1}{2n})$, flat edge of angle $\pi$, and the target sum $\pi (1+\frac{1}{2n})$ are all clean. Thus we cannot use any angles $\in \{\alpha ,\beta \}$ to fill the deficit.

This leaves only the flat edge of angle $\pi$ and two convex angles: the shuriken tip of angle $\frac{\pi }{n}$ and the wheel corner of angle $\pi (1-\frac{1}{2n})$. If we used only copies of the tip $\frac{\pi }{n}$, we would get an even multiple of $\frac{\pi }{2n}$, but the target sum $\pi (1+\frac{1}{2n})$ is an odd multiple of $\frac{\pi }{2n}$. Using a flat edge $\pi$ would leave a gap of angle $\frac{\pi }{2n}$, which is too small to fill with any of the available angles. Finally, using the wheel corner $\pi (1-\frac{1}{2n})$ (gluing a second wheel to the first) will leave a gap of angle $\frac{\pi }{n}$, which can only be filled by the tip angle $\frac{\pi }{n}$.

Thus we have shown that, in all cases, the wheel’s convex angle $\pi (1-\frac{1}{2n})$ has to be matched with an anticorner or a tip of the shuriken. Furthermore, an edge of the wheel adjacent to a corner must be glued to an edge of the concave chain adjacent to a tip or anticorner of the shuriken. We can follow the path of both the wheel and the concave chain of the shuriken and observe that the $n-2$ anticorners and the two tips of that concave chain will be glued to consecutive corners of the wheel.

At the end of the concave chain of the shuriken, we find a tip glued to the corner of a wheel, leaving a deficit of $\pi (1-\frac{1}{2n})$ to fill. As shown in Lemma 3.4, this can only be filled by another wheel corner. Therefore, the surround of a wheel must be filled by an alternating sequence of wheels and shurikens (omitting the small gaps left between the tweedles and the notches, which are filled by staples).

Pick one wheel $T$ in the tiling, translate the tiling so that its center³³3Define the center of a wheel to be the center of gravity of its $4n$-gon, without adornments. is at the origin $(0,0)$, and rotate the plane so that edge $i$ of its $4n$-gon is glued to another wheel at a horizontal edge of the $4n$-gon, with $T$ below that edge. Also rescale so that the width of a wheel’s $4n$-gon (the distance between parallel edges, without adornments) is $1$. Then the wheel adjacent to edge $i$ of $T$ will have its center at coordinate $(0,1)$. Following the boundary of $T$ clockwise, we find a shuriken glued to the edges $i+1,\mathrm{\dots },i+n-1$ of $T$, and a wheel glued to the edge $i+n$ of $T$. The wheel glued to edge $i+n$ has its center at coordinates $(1,0)$. Continuing this reasoning, we find that the tiling is a grid of wheels with centers on all integer lattice points. The shurikens and staples ensure that all spaces are filled, and the tweedles ensure that the tiles are compatible as in a Wang tiling. Therefore, for any tiling with the three tiles, we can produce a tiling of the plane with the original Wang tiles. $◀$

Combine Lemma 3.1 (if) and Lemma 3.5 (only if). $◀$

Combining this with membership of the tiling problem in co-RE (to be proved in the next section), we obtain:

In a recent paper, Greenfeld and Tao [8] consider a generalized version of the tiling problem, where only a periodic subset of space needs to be covered by the tiles. In our reduction, the union of the shurikens form a periodic subset of ${ℝ}^2$, and so does its complement. Thus, tiling the complements of the shurikens with the two remaining tiles is undecidable:

By plugging in Wang tiles that simulate a universal Turing machine, such as Robinson’s 36 Wang tiles [13], we also obtain undecidability of tiling completion with three specific tiles:

We implemented our construction in an open-source web application [4], where the user can input any set of Wang tiles and see the resulting polygons. Figure 6 shows the output for the 11 Wang tiles from Figure 1.

Pick a generic quadrilateral, and glue a very flat isosceles triangle to one of its edges, where the apex angle is ${180}^{\circ }-r/100$ for a given constructible number $r\in [0,1]$. The other angles and edge lengths of the triangle are constructible via trigonometric functions.

The resulting pentagon tiles the plane only in the degenerate case where the triangle is degenerate, i.e., a line segment, which happens exactly when the obtuse angle of the triangle is exactly ${180}^{\circ }$. Thus the tiling problem is equivalent to testing whether $r=0$ for a given constructible number $r\in [0,1]$, which is co-RE-hard as shown above. $◀$

Of course, this result is quite unsatisfying, as the reason for undecidability stems from the extreme weakness of the model and generality of the representation of the polygons, and the inability to even check locally that a tiling is valid. Yet surprisingly, in this same model, we are able to show membership in co-RE.

For the (a) statements, translate (and rotate) the tiling so that one of its tiles is anchored; and if we are given a seamless patch $P$, choose to anchor one of its tiles. Consider the disk $D_{r+2\rho }$ of radius $r+2\rho$ centered at the origin (the anchored tile’s center of gravity). Take all the tiles in the plane tiling that are fully inside $D_{r+2\rho }$, and take all the tiles of $P$ (if given). Because the tiles do not overlap and are each of area $\ge A_{\min }$, there are at most $\pi {(r+2\rho )}^2/A_{\min }$ tiles inside $D_{r+2\rho }$. Take the connected component that contains the origin (and thus the tiles of $P$, if given), which only decreases the number of tiles. This is an anchored patch that covers the smaller disk $D_r$.

For the (b) statements, build the incidence graph on the tiles of the carpet, where two tiles are connected by an edge if they share a vertex. If this graph is connected, then the patch is seamless. If this graph is disconnected, it is because of seams. Seam lines cannot intersect: otherwise, their intersection point is a vertex common to both sides of the seams. Thus, cutting the patch along all seams, or equivalently taking one connected component of the incidence graph, will create neat vertices on the new boundary, where the seams were. Take the component that contains a tile covering the origin. This is a seamless patch that is neat within radius . $◀$

Consider the intersection between the carpet $C$ and the disk $D_{r+2\rho }$, which might have multiple connected components and/or be self-overlapping. Pick the component $S$ that contains the anchored tile. The boundary of $S$ is composed of straight lines (the edges of the tiles connected by neat vertices) and circular arcs (portions of the boundary of $D_{r+2\rho }$), connected together at convex angles. Thus $S$ is convex, so non-self-overlapping.

Back in the carpet, remove all tiles that are not entirely contained in $D_{r+2\rho }$. Again, this possibly results in several connected components. Retain the component $C^{\prime }$ that contains the anchored tile, where connectivity is defined by interior paths, so that $C^{\prime }$ does not have pinch points. By construction, this component is contained in $S$ and thus is not self-overlapping. Also $C^{\prime }$ is a topological disk: a hole in $C^{\prime }$ could only come from a removed tile, which must touch the outside of $D_{r+2\rho }$, contradicting that it is surrounded by $C^{\prime }$ (by planarity). Therefore, $C^{\prime }$ is a patch.

Finally, because all tiles removed have diameter $\le 2\rho$, none of the deleted tiles intersect the disk $D_r$, and therefore all vertices within radius remain untouched. Therefore the patch $C^{\prime }$ is neat within radius . $◀$

Suppose we have a carpet that is neat within radius . By Lemma 4.9, we have a patch that is neat within radius . The intersection of the patch and the disk $D_r$ is a disk cut by noncrossing chords; refer to Figure 7. Note that any chord of $D_r$ that intersects $D_{r/2}$ cuts off an arc of angle $\frac{2}{3}\pi$ from $D_r$. Because the chords defined by the patch do not intersect in $D_r$, at most two of them intersect $D_{r/2}$.

If no chord intersects $D_{r/2}$, then the patch covers $D_{r/2}$, and we are done.

If exactly one chord intersects $D_{r/2}$, then the patch is contained in a half-plane that contains the origin and is bounded by the extension of the cord. Rotate a copy of the patch by ${180}^{\circ }$ about the center of the cord, and glue the two pieces together. This produces a patch that covers $D_{r/2}$.

If two chords intersect $D_{r/2}$, then the patch is contained in a wedge defined by the extensions of the two chords. Let $q$ be the apex of the wedge, and assume $q$ is on the $x$ axis, with one of the chords above the $x$ axis and the other chord below. Assume without loss of generality that the chord below is the longest one. Repeatedly stitch copies of the patch by rotating it about $q$, upward, gluing the longer chord of the previous copy to the shorter chord of the next copy, until the upper half of $D_{r/2}$ is covered. Now repeat the procedure for a single chord. The resulting patch covers the disk of radius $r/2$. $◀$

We translate the above theorem to seamless anchored patches.

For every positive integer $k$, set $r=k\rho$ and use Lemma 4.8 to determine whether there exists an anchored carpet that is neat within radius , or whether $P$ can be completed to produce such a carpet. This is a recursively enumerable disjunction of co-RE problems, so by Lemma 4.4 is in co-RE. By Lemma 4.12, if all of these problems output true, then the polygons tile the plane or complete $P$ to tile the plane. By Lemma 4.8, if any of these problems outputs false, then the polygons do not tile or complete $P$ to tile the plane. $◀$