Suppose and are two polygons, possibly self-intersecting. Suppose no three out of vertices of and lie on the same straight line. Find the largest possible number of intersections of and .
Details and assumptions
You should not count any self intersections of the polygons.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
First, note that each side of A can intersect with no more that 1 6 sides of B . Indeed, consider the line that contains it. It divides the plane into two parts. If B i B i + 1 intersects it for all i from 1 to 1 6 , then B 1 and B 1 7 are in the same half-plane so B 1 7 B 1 cannot intersect it. Therefore, the total number of intersections can be at most 1 6 × 1 7 = 2 7 2 .
To construct an example with 2 7 2 intersections, consider 3 4 points uniformly distributed on the unit circle, with angles to the x -axis being 3 4 , 2 π k for k = 0 , 1 , . . . , 3 3 . We will call these points P k .
The heptadecagons A and B will be "stars", with A using even k and B using odd. Specifically, the edge from A i to A i + 1 or from A 1 7 to A 1 is the segment from P k to P k + 1 6 ( m o d 3 4 ) for some k . Then B is obtained from A by rotating at an angle of 3 4 2 π about the origin. The picture below illustrates this construction with pentagons instead of heptadecagons.
Note that all edges of A and B are chords that are "close" to a diameter. One can see that for a given edge of A exactly one edge of B does not intersect it: the one that is obtained from it by the symmetry around the origin. For example, for the chord A 1 A 2 that connects points P 0 and P 1 6 , at most one of the endpoints of an edge of B can be among P 1 , P 3 , . . . , P 1 5 . If neither are there, then the only way to have a chord this close to the diameter using the points P 1 7 , . . . , P 3 3 is to use P 1 7 and P 3 3 .
So, the final answer is 2 7 2 .