Consider all polygons whose vertices are lattice points and edges are parallel to the axes such that no more than two edges meet at a vertex. For two polygons A and B, define A+B be to the set of polygons which can be partitioned into two poygons congruent to A and B.

Given two polygons A and B of same area. Do there always exist a polygon P such that , there is a polygon X in A+P and Y in B+P such that X is congruent to Y? What can we say about area of P?

Edit: I wanted to ask a more general question. If such a P exists, how will one go on constructing it?,And how to characterize the pairs for which such a P does not exist? Is this a known problem?? etc


Define an inclusion of a polygon $A$ to be a subset of the complement of the polygon whose boundary minus $A$ consists of a single edge. Inclusions sometimes contain other inclusions. The congruence class of an inclusion is the congruence class of the pair (polygon, free edge). Define the inclusion vector $Iv(A)$ to be the nonngegative linear combination of congruence classes of inclusions of $A$ describing all inclusions up to congruence.

Notice that for any $X$ in $A + P$, as long as neither $A$ nor $P$ fit inside an inclusion of the other, then $Iv(X) \ge Iv(A) + Iv(B)$

Let's say that a polygons $X$ and $Y$ bind to each other with strength $k$ if they can be arranged up to congruence so that their intersection is a connected set of $k > 2$ edges. Then any inclusions $J$ of an element $X$ of $A + P$ that are not inclusions of $A$ or of $P$ must be polygons that bind to $A$ and $P$ with total strength at least the (length of the perimeter of $J$) - 1.

With the picture established by all these definitions, it's easy to make counterexamples. For $A$ and $B$, start with large rectangles with crenelated boundaries (every other square along the boundary removed). There are necessarily 4 straight segments of length 2 on the boundary at the 4 corners, but that is all. Now bore out at least 5 maximal inclusions from $A$ and $B$ in the form of $S$-patterned double spirals that do not bind to $A$ or $B$ anywhere except at the four straight stretches. Make sure the maximal inclusions removed from $A$ and $B$ are not congruent, and that the resulting polygons $A'$ and $B'$ have the same area.

The difference between the vectors $Iv(A)$ and $Iv(B)$ is sufficiently large that adding a polygon $P$ can never create enough inclusions to bridge the difference.

  • $\begingroup$ I am having difficulty understanding this: "a subset of the complement of the polygon whose boundary minus $A$ consists of a single edge." Do you mean, "whose boundary minus the boundary of $A$"? Or do you mean, "whose boundary minus the set of points enclosed by $A$"? Likely the former? If so, the boundary of this polygon (call it $A'$) differs from $A$ in exactly one edge, and $A'$ could be a superset or a subset of $A$, or neither. $\endgroup$ – Joseph O'Rourke Oct 31 '10 at 3:02
  • $\begingroup$ @Joeseph O'Rourke. Sorry for being cryptic. I mean that $J$ is an inclusion of $A$ when the filled polygon $J$ intersect the filled polygon $A$ consists of all but one edge of $J$. If you think of $A$ as an island, an inclusion is a bay that can be cut off by a single edge. $\endgroup$ – Bill Thurston Oct 31 '10 at 12:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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