7
$\begingroup$

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:


          StomachParts
          (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?

$\endgroup$
2
  • 3
    $\begingroup$ Why would the finiteness reduction not be evident? You must start the gluing-together at corners for each "interior segment". $\endgroup$
    – domotorp
    Apr 24, 2016 at 5:13
  • $\begingroup$ @domotorp: Oh, you are right---Thanks! $\endgroup$ Apr 24, 2016 at 11:51

1 Answer 1

10
$\begingroup$

$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.

$\endgroup$
1
  • $\begingroup$ Isn't 1) a bit of an overkill? I mean after we know the whole combinatorial structure, it is obvious that we can have only one realization. $\endgroup$
    – domotorp
    Apr 24, 2016 at 5:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.