2

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

flag

1 Answer

7

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.

link|flag
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. – Joseph O'Rourke Oct 31 2010 at 3:02
@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. – Bill Thurston Oct 31 2010 at 12:01

Your Answer

Get an OpenID
or

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