Skip to main content
replaced http://mathoverflow.net/ with https://mathoverflow.net/
Source Link

Triggered by the MO question, "How many convex shapes can be made with the pieces of the Stomachion?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][1]][1]
          (Image from [Bernd Karl Rennhak](http://www.logelium.de/Stomachion/StomachionPuzzel_EN.htm).)
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?

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][1]][1]
          (Image from [Bernd Karl Rennhak](http://www.logelium.de/Stomachion/StomachionPuzzel_EN.htm).)
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?

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][1]][1]
          (Image from [Bernd Karl Rennhak](http://www.logelium.de/Stomachion/StomachionPuzzel_EN.htm).)
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?
added 67 characters in body
Source Link
Joseph O'Rourke
  • 150.9k
  • 36
  • 358
  • 958

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][1]][1]
          (Image from [Bernd Karl Rennhak](http://www.logelium.de/Stomachion/StomachionPuzzel_EN.htm).)
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?

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][1]][1]
          (Image from [Bernd Karl Rennhak](http://www.logelium.de/Stomachion/StomachionPuzzel_EN.htm).)
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.

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][1]][1]
          (Image from [Bernd Karl Rennhak](http://www.logelium.de/Stomachion/StomachionPuzzel_EN.htm).)
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?
Source Link
Joseph O'Rourke
  • 150.9k
  • 36
  • 358
  • 958

Decidability of convex rearrangements of polygons

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][1]][1]
          (Image from [Bernd Karl Rennhak](http://www.logelium.de/Stomachion/StomachionPuzzel_EN.htm).)
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.