Decidability of convex rearrangements of polygons

Question

Triggered by the MO question, "How many convex shapes can be made with the pieces of the Stomachion?," I would like to pose this question:

Q. Given $n$ polygons in a set $S$, say each with integer coordinate vertices, is there some algorithm to count/list the number of ways that some subset of $S$ of these polygons could be fit together, with pairwise disjoint interiors, such that their union is a convex polygon?

The polygons may be rotated and translated in the fitting-together. One might restrict the polygons in $S$ each to be convex. Specifying integer coordinates is meant to make the input to the question of finite length, say, $L$ bits.

Examples from the page that j.c. found:

---

         
          ^{(Image from Bernd Karl Rennhak.)}

---

The difficulty is that it is not immediately evident how to reduce the problem to a finite set of possibilities to try, for the gluing-together need not be whole-edge to whole-edge. Maybe decidability of 1st-order theories of reals can be applied?

Answer 1

$1)$ To answer your finiteness question - this is pretty standard. There is a finite number of combinatorial arrangements of tiles. Each leads to a system of linear equations which can be solved. Even if you are working over $\Bbb R$, you have only finitely many irrationalities over $\Bbb Q$, so it is still a finite problem.

More precisely, suppose the polygon side lengths are presented as

$(p_0/q_0) + (p_1/q_1)\alpha_1 + \ldots + (p_k/q_k)\alpha_k$

with some $p_1,q_i \in \Bbb N$ and rationally independent $\alpha_i$. From the combinatorial arrangement, built a dual network with unknown weights corresponding to intersection lengths. Write linear equations (side = sum of its parts in the intersections) which can be viewed as a vector equations in $\Bbb Q\langle\alpha_1,\ldots,\alpha_k\rangle$. Solve this system for non-negative variables. Done.

$2)$ For the complexity part of your question, I am pretty sure the counting is #P-hard. Suppose for a minute that your tiles are polyominoes. The only convex regions they can form are rectangles. Deciding if a set of polyominoes tiles a rectangle is known to be hard for several variations of this problem. Jed Yang proves that rectangular tileability is undecidable when tiles are allowed to be repeated. Demaine and Demaine prove NP-compleness when the tiles are non repeated, but the rectangle is fixed. There are many more refs I am missing some mentioned in these papers.

Back to convex polygons. Well, subdivide each polyomino into small tiles with irrational edge lengths and side angles so the only way they can fit each other is by forming polyominoes first. For example, take a point slightly off-center in each polyomino square and take a triangle over an edge which you attach to the triangle on the the other side whenever two squares are adjacent.

Now, you have a large collections of triangles and quadrilaterals. Some pairs of small triangles can easily form a convex region; these small tilings are easy to count. But large convex regions are all rectangles which are hard to count.