Question P.169: Suppose we are given an m-gon and an n-gon in the plane. Con......
Suppose we are given an m-gon and an n-gon in the plane. Consider their intersection; assume this intersection is itself a polygon.
a. If the m-gon and the n-gon are convex, what is the maximal number of sides their intersection can have?
b. Is the result from (a) still correct if only one of the polygons is assumed to be convex?
a. The maximal number of sides that the intersection of a convex m-gon and a convex n-gon can have is m + n. To see why more than m + n sides is not possible, first note that any side of the intersection must be part or all of one of the sides of one of the two original polygons, and that there are m + n sides in all of the two original polygons. Thus if the intersection had more than m + n sides, at least two of these would have to be part of the same side of one of the original polygons, which cannot happen because the polygons are convex and hence have convex intersection. Therefore, the intersection can have at most m + n sides.
To show that there really can be m+n sides, we will assume n ≥ m ≥ 3. We will start with a regular (m + n)-gon R and show that one can find a convex m-gon X and a convex n-gon Y whose intersection is R. An example will help illustrate the idea. If m = 3 and n = 5, then the regular octagon R is the intersection of triangle ABC and pentagon DEF GH, as shown.
As in the example, the idea in general is to get the m-gon and the n-gon by extending suitable sides of R; we have to make sure that the sides will intersect when we expect them to and that the resulting polygons are convex. So we want to be able to divide the m + n sides of R into two groups: m of the sides will be parts of sides of X while the other n will be parts of sides of Y . If two adjacent sides of R are both parts of sides of X, the vertex where they meet will be a vertex of X, and similarly for Y . On the other hand, if for two adjacent sides of R one is part of a side of X and the other is part of a side of Y , then both these sides get extended beyond the vertex until they meet the extensions of the “next” sides of X, Y respectively.
To make sure that two successive (parts of) sides of X always meet when they are extended, it is enough to make sure that one is less than halfway around the regular (m + n)-gon R from the other; the angle at which these sides meet is then certainly less than 180°. So we will have our convex polygons X and Y by choosing m of the sides of R to be sides of X and the others to be sides of Y , provided we can do this in such a way that two successive sides of X or of Y are never halfway or more around the (m + n)-gon from each other.
If m + n is even, such an assignment can be carried out by choosing two opposite sides of R, designating one of them as a side of X and the other as a side of Y , and then designating the sides adjacent to each of the two chosen sides as belonging to the polygon which that chosen side does not belong to (see figure). This works since m ≥ 3, n ≥ 3; the other sides can be designated at random in such a way as to end up with m sides of X and n sides of Y .
If m + n is odd, there are no “opposite sides” of R, but we can designate a side and the two sides adjacent to the opposite vertex as sides of X, then designate the four sides adjacent to these three chosen sides as sides of Y (see figure). This works because m ≥ 3, n ≥ 4. Once again, all other sides can be designated arbitrarily so as to end up with m sides of X and n sides of Y .
b. No. The following diagram shows that the intersection of a nonconvex 4-gon and a convex 3-gon can be an 8-gon.
