WorksMathematics
Intersections of Odd Polygons Revisited
Abstract
It is shown that the maximum number of intersection points between the boundaries of a simple -gon and a simple -gon is for any odd integers . The previous best upper bound was , for some huge constant .
Introduction
Let and be two simple polygons with and sides, respectively. We are interested in the very basic question of determining the maximum number of distinct intersection points between the boundaries of and . We assume that no two sides of the polygons overlap, therefore, this number is finite and is upper-bounded by . It is easy to see that this bound can be attained when and are both even, see Figure 1(a) for an example. Observe also that if is odd, then every side of has at most distinct intersection points with sides of , therefore there are at most intersections between sides of and . It is not hard to construct an -gon and an -gon admitting that many intersections for every even and odd , see Figure 1(b) for an example. In contrast, determining the maximum number of intersections between the boundaries of two odd size polygons is much more challenging.
Figure 1. (a) Optimal construction for , with intersections. (b) Optimal construction for , , with intersections. (c) Lower-bound construction for , , with intersections.
This problem was first studied by Dillencourt, Mount, and Saalfeld [3]. They showed a construction with intersections (see Figure 1(c) for an example) and claimed that this bound is tight, however, their proof contained an unrecoverable error. A weaker upper bound of for was proved by Černý, Kára, Král’, Podbrdský, Sotáková, and Šámal [2]. This was improved to , where is a (huge) constant, in joint work Keszegh and Rote [1]. Recently, the author revisited this work with ChatGPT, asking it whether that proof is sound and whether the constant can be decreased, hopefully, down to 3. The outcome of the first question was a small gap revealed in a certain case-analysis in the proof of the main theorem where one subcase was overlooked (see Appendix § 6). Still, it seems that by a more careful and finer analysis this gap can be resolved. As for the second question, using tools from [1], ChatGPT indeed managed to decrease the constant : first, to 11 while also providing a simpler proof than the one in [1]. Then, with some extra effort and case-analysis, down to 3, thus determining the exact maximum possible number of intersections between two odd size simple polygons.
Theorem 1.1. For any odd integers , the maximum number of intersection points between the boundaries of a simple -gon and a simple -gon is .
While preparing this manuscript the author was contacted by Ju Yong Seo who published a different proof of Theorem 1.1 obtained using a different LLM [4]. In fact, the result in [4] is stronger, since it states that the so-called disjointness graph of the two polygons has at most three connected components and this immediately implies Theorem 1.1 (see § 2). However, the proof in [4] is computer-assisted (in the pre-LLM era sense), as it boils down to verifying a few hundred cases using a SAT solver, whereas the proof presented here can be verified by hand. Furthermore, we present a simple proof (relying on [1]) of the slightly weaker bound .
Organization. We first establish terminology and some tools in Section 2. Using these tools we present a simple proof of the weaker bound in Section 3. Section 4 introduces further definitions and tools that are required for proving the optimal bound which is then proved in Section 5. The small gap in the proof in [1] is described in Appendix A.
AI Disclosure. ChatGPT-6 Astra was used for proving the new result and for preparing this manuscript. The author verified the proofs, simplified some of them, edited the paper considerably to improve the presentation, and takes full responsibility for its content.
Assumptions, terminology, and tools
Throughout this paper denotes a simple -gon and denotes a simple -gon, where and are odd integers. We assume that each side of intersects each side of in at most one point. Furthermore, it follows from [1] that we may assume, without loss of generality, that each intersection point of two sides lies in the interior of both sides (that is, it is a crossing point), no three vertices of and combined are collinear, and that no two sides of and combined are parallel. Denote by the number of intersection points between a side of and a side of .
The disjointness graph . As in [1, 2], we define the disjointness graph of and . It is a bipartite graph, , whose vertex set corresponds to the sides of and and its edge set consists of pairs of disjoint sides, one from and the other from . See Figure 4 for an example. By abuse of notation we interchange sides of the polygons with their corresponding vertices in .
Figure 4. Two heptagons and , their disjointness graph , and their transitions graph . The edges of are associated with three gadgets: the -pure gadget , the -pure gadget and the double gadget .
Let be the number of connected components of . Since every edge in corresponds to a non-intersecting pair of sides, it follows that . Note that , and therefore . Thus, we have:
The upper bound in [1] follows by showing that . The current improvement of this bound is obtained by showing that many connected components imply many additional edges within connected components. Clearly, once the number of edges in a graph exceeds the number of vertices minus one, any additional edge within a connected component implies a new cycle. It is therefore convenient to consider the cycle rank of and its connected components. For a graph the cycle rank of (also known as circuit rank or cyclomatic number) is the minimum number of edges one has to remove from to make it acyclic (that is, a forest). We recall the following facts about the cycle rank of a graph, which we denote here by .
Proposition 2.1. Let be a graph, possibly with parallel edges. Then , where is the number of connected components of . Furthermore, is non-negative, does not decrease when adding vertices or edges, and remains the same when contracting a non-loop edge. If have disjoint edge sets, then .
Proof. If , that is is connected, then clearly since one has to remove edges to get a spanning tree with edges. If , then by applying this argument for every connected component and summing up we get the desired equality.
By definition is non-negative and can only increase when adding vertices or edges. Contracting a non-loop edge decreases both the number of vertices and the number of edges by one while leaving the number of connected components unchanged, therefore . It is also easy to see that , since breaking every cycle in requires in particular breaking every cycle in and every cycle in .
Since , we have:
Therefore, we can get a better upper bound on by showing that has few connected components or that its cycle rank is high. More precisely, Theorem 1.1 will follow once we show that . In fact, it is enough to show that by the following observation.
Proposition 2.2. is odd.
Proof. The number of crossings between two Jordan curves is even, thus is even. Since is odd and is even, it follows from (2) that is odd.
We proceed with some other useful notions and lemmas from [1]. Let and be two consecutive polygon-sides sharing a common endpoint . Denote by the convex cone which is bounded by the two rays emanating from and containing and , respectively, and let denote the opposite cone (see Figure 2).
Figure 2. The cones defined by two consecutive polygon-sides and .
Observation 2.3. Let and be two consecutive polygon-sides and let be a polygon-side that crosses both and . Then no endpoint of lies in .
The following lemma gives rise to the main geometric structure used throughout the proof.
Lemma 2.4 ([1 Lemma 5]). Let and be two consecutive sides of one polygon such that there is no side of the other polygon which is disjoint from both of them. Then there are two consecutive sides of the other polygon, and , such that and . Furthermore, or .
We remark that the original statement of this lemma in [1] assumes that and belong to different connected components of , however, its proof only uses the property stated here which is implied by the different components assumption.
Gadgets and hooking types
Let and be two consecutive sides of and let and be two consecutive sides of such that , and or (see Figure 3 for examples). The two pairs of consecutive edges are called associated pairs in [1]. Here we refer to them as a gadget and say that and are its base edges, or simply bases. As a convention, we denote a gadget by a 4-tuple such that are its -pair, are its -pair, and are its base edges. Note that by definition we get the same set of gadgets if we interchange and .
Figure 3. A gadget . (a) A pure -hooking gadget. (b) A pure -hooking gadget. (c) A double gadget. (d) The base edges of the gadget. (e) Not a gadget since no hooking occurs.
If the common endpoint of the -pair (resp., -pair) of a gadget lies in the cone of the -pair (resp., -pair), then we say that the gadget is -hooking (resp., -hooking). Note that a gadget may be both -hooking and -hooking and that a pair of consecutive sides may participate in several gadgets (of similar or different hooking types). If exactly one hooking occurs in a gadget, then we say that this gadget is pure and otherwise if the two hookings occur the gadget is double. See Figure 3 for illustrations.
Observation 2.5. Let be a gadget.
If is pure -hooking, then and .
If is pure -hooking, then and .
If is double hooking, then and .
Corollary 2.6. contains no isolated vertices.
Proof. Suppose for contradiction that there is a polygon-side which is an isolated vertex in . Let be a side of the same polygon that is consecutive to . Then it follows from Lemma 2.4 that there is a side of the other polygon such that , a contradiction.
The following lemma is crucial for the proof.
Lemma 2.7 ([1 Lemma 7]). Suppose that two gadgets use eight distinct sides and induce a subgraph of which is a matching consisting of their four base edges. Then both gadgets are pure and of different hooking types.
Remark. We note that the original statement of this lemma refers to the case where the four base edges belong to different connected components of , however, the proof actually uses the weaker assumption stated here.
A weaker upper bound
Recall that it is enough to show that . In particular we may assume that .
The transitions graph . Define a graph as follows: the node2 set of consists of the connected components of and its edge set consists of pairs of distinct connected components and such that there are two consecutive -sides and such that and . By Lemma 2.4 there is at least one gadget whose -pair is . We say that any such gadget and are associated and note that the gadget has one of its base edges in and its other base edge in . See Figure 4 for an example.
Remarks. It easily follows from its definition that is connected. Observe that a gadget is associated with at most one edge of , but several gadgets may be associated with the same -edge. The fact that an -edge corresponds to a gadget and the symmetric roles that and
play with respect to gadgets imply that defining the transitions graph according to would result in the same graph .
Lemma 3.1. There are no two node-disjoint edges of associated with two gadgets that are both -hooking or both -hooking.
Proof. Suppose that has two disjoint edges associated with same-type gadgets and . Then the four bases of and lie in four distinct connected components, thus, their eight vertices induce a matching in . But then by Lemma 2.7 the two gadgets must have different types.
Lemma 3.2. If two gadgets that join a component to two distinct other components are both -hooking or both -hooking, then their bases in are connected by an edge of or share a vertex.
Proof. Suppose that there are two gadgets sharing the same type and and three distinct connected components such that lies in and lies in , for (see Figure 5 for an illustration). It is enough to consider the case that and , for otherwise the claim trivially holds. Consider the three subsets , and , and observe that there cannot be edges in between vertices from different subsets, since they belong to different connected components. If , then the subgraph induced by those eight vertices is a matching and by Lemma 2.7 the two gadgets cannot share a hooking type, a contradiction.
Figure 5. An illustration for the proof of Lemma 3.2: the gadget consists of the -pair and the -pair , its base edges and are in and , respectively. It follows that and share a vertex or are connected by an edge of .
The following is an important consequence of Lemma 3.2.
Corollary 3.3. Let be a connected component containing pairwise vertex-disjoint bases belonging to gadgets sharing the same hooking type where each of these gadgets is associated with an -edge connecting to a distinct connected component. Then the vertices of the bases induce a subgraph of with vertices and at least edges. In particular, .
In order to use Corollary 3.3 we first consider a spanning tree of . Clearly, consists of exactly edges. For every edge of , we select one gadget associated with , and color with color if this gadget is -hooking, and with color otherwise (if it is -pure). Let and be the subgraphs consisting of the edges colored and , respectively. Recall that by Lemma 3.1 any two edges of associated with same-type gadgets share a common node of . It follows that apart from isolated nodes, each of and is a star.3 Let and be the centers of the stars and , respectively (if one of these stars is empty, then we choose an arbitrary component as its center). Note that it may happen that .
Obtaining disjoint base edges in and . For each edge of , we mark its base edge in that belongs to the gadget selected for . Then we do the same for edges of and their corresponding base edges in . If a base edge belongs to two selected gadgets, then we mark it twice. Considering the subgraph of that consists of these marked edges (possibly with parallel edges), note that its maximum degree is at most two. Indeed, suppose without loss of generality that a -side in belongs to three marked bases , and . Let be the corresponding gadget and let be the associated -edge, for . Note that these are three distinct -edges, since we selected one gadget per tree edge. Then is a consecutive side of and belongs to , for . But has only two consecutive sides.
It follows that the subgraph of marked bases consists of paths and even cycles (possibly 2-cycles). Therefore, its edge set can be partitioned into two matchings by picking every other edge in a path or a cycle. It follows that there is a matching such that each of its (marked base) edges lies in or and
Finishing the proof. Let (resp., ) denote the base edges in that belong to selected gadgets that are associated to edges of (resp., ). Set and . Considering the subgraph of that is induced by the endpoints of the edges in , it follows from Corollary 3.3 that its cycle rank is at least .4 Similarly, the cycle rank of the subgraph of induced by the endpoints of the base edges in is at least . Since these two subgraphs are edge-disjoint and , it follows from Proposition 2.1 and (3) that and by (2) we get that as claimed.
More tools for proving the optimal bound
Before proving the optimal upper bound on in Section 5, we collect further useful claims.
Proposition 4.1. Let be three lines in general position and let denote their arrangement. Let be the single (triangular) bounded face of and let be an edge of . For , let be a straight-line segment with one endpoint in the unbounded face whose intersection with is and its other endpoint lies in the unbounded face whose intersection with is its edge opposite to .5 If each of and crosses , then and cross each other.
Proof. By applying an appropriate affine transformation we may assume without loss of generality that is the -axis, is the -axis, is the line , and . We denote the unbounded faces by in clockwise manner, such that shares the edge with . We may assume that the endpoints of lie in and and the endpoints of lie in and . See Figure 6. Following from its endpoint in it enters at a crossing point with , denote it by , . Similarly, following from its endpoint in it enters at a crossing point with , denote it by , . If , then and cross at . If , then and must cross inside , since their crossing points with its boundary alternate. Otherwise, if , then and must cross inside since their crossing points with its boundary alternate. □
Figure 6. An illustration for the proof of Proposition 4.1: If crosses and its endpoints are in and and crosses and its endpoints are in and , then and cross.
Definition 4.2 (near edges). Let be a graph and let and be two distinct edges in . We say that and are near, if they share a vertex or there is an edge between an endpoint of and an endpoint of .
Thus, Lemma 3.2 shows that there are near bases provided certain assumptions hold. The following will be useful later on.
Proposition 4.3. In a tree :
(a) For every non-empty set of pairwise near edges in , there is an edge such that every edge in the set has or as an endpoint. In particular has no three pairwise near edges that form a matching; and
(b) if and are two non-near edges, then a non-empty set of edges that are near each of and forms a star.
Proof. Let be a set of pairwise near edges in . If every pair of edges shares a vertex, then is a star (it cannot be a triangle), and we can pick any edge in as . Otherwise, let and be vertex-disjoint edges and let be the edge connecting them. Suppose that there is an edge with no endpoint in . Considering the connected components of , belongs to one of them which does not contain at least one of and , since they belong to different components. Assume without loss of generality that and belong to different components. Then a path connecting them in must go through but only one of them is incident to this edge. Therefore and are not near.
As for the second part of the claim, consider the unique path in connecting and and let be a vertex on this path which is not an endpoint of any of them (there must be such a vertex since and are not near). We claim that every edge which is near both and must have as an endpoint. Indeed, suppose that there is an edge which is near both and and is not one of its endpoints. Considering the connected components of , belongs to one of them which does not contain at least one of and , since they belong to different components. Assume without loss of generality that and belong to different components. Then a path connecting them in must go through and therefore they are not near edges.
By Lemma 3.2 two side-disjoint gadgets spanning three connected components must be of different pure types or force an edge between their base edges in their common connected component. The following claim complements this by showing that if the gadgets are both pure, then they do not share sides.
Proposition 4.4. Let and be two gadgets and let be three distinct connected components of such that lies in and lies in , for . Then:
if , then both gadgets are -hooking and at least one is also -hooking;
if , then both gadgets are -hooking and at least one is also -hooking; and
if and , then both are double.
Consequently, if and are pure, then their bases in are vertex-disjoint.
Proof. Suppose that . Apply an affine transformation of the plane such that the triangle whose vertices are , and is mapped to the triangle whose vertices are , and , respectively. Note that if a point lies in a convex cone , then the image of is a convex cone and the image of lies in it. Therefore, intersections and hooking-types remain the same under this transformation.
We first claim that no gadget is -pure. Suppose without loss of generality that is -pure. Since is -hooking, . Since is not -hooking must lie inside the triangle whose corners are , and , see Figure 7. However, then which implies that cannot cross both and by Observation 2.3. Thus, or , a contradiction.
Figure 7. An illustration for the proof of Proposition 4.4: If and is -pure, then cannot cross both and .
Therefore, both gadgets are -hooking and it remains to show that at least one of them is also -hooking. Suppose that both of them are -pure. We proceed by considering whether lies above or below the -axis and whether it has a positive or negative slope. Consider the arrangement determined by the three lines through , and : it contains one bounded triangular face, denote it by , and six unbounded faces. Denote these unbounded faces by according to their clockwise order and such that has as one of its bounding edges.
Suppose that lies below the -axis and has a negative slope, see Figure 8a. Then and must lie in this face by Observation 2.5 since is -pure. However, then which implies by Observation 2.3 that cannot cross both and , as it should.

Figure 8. (a) If has a negative slope, then and therefore cannot cross both and . (b) If has a positive slope, then and therefore cannot cross both and . Figure 8: Illustrations for the proof of Proposition 4.4: lies below the -axis.
Suppose that lies below the -axis and has a positive slope, see Figure 8b. Then and must lie in this face by Observation 2.5 since is -pure. However, then which implies that cannot cross both and , as it should.
Suppose that lies above the -axis and has a positive slope, see Figure 9a. Since is -pure, by Observation 2.5. Because crosses and , it follows that has one endpoint in and its other endpoint in . Similarly, since is -pure, . Because crosses and , it follows that has one endpoint in and its other endpoint in . However, then and cross by Proposition 4.1, which is impossible.
Figure 9. (a) has a positive slope. (b) has a negative slope. Figure 9: Illustrations for the proof of Proposition 4.4: lies above the -axis.
Suppose that lies above the -axis and has a negative slope, see Figure 9b. Since is -pure, by Observation 2.5. Because crosses and , it follows that has its other endpoint in . Similarly, since is -pure, . Because crosses and , it follows that has its other endpoint in . However, then and cross by Proposition 4.1, which is impossible.
This concludes the case that . The case that is symmetric, and the case that and follows from the two previous cases. It also follows that if and are pure, then and .
Next, we establish further properties of the transition graph .
Proposition 4.5. For every partition of the nodes of into two disjoint subsets and such that and there are two gadgets crossing the cut with vertex-disjoint bases in .
Proof. Observe first that there cannot be just one -side in a component from that is part of every gadget crossing the cut. Indeed, suppose that there is such a side and let be the connected component of that contains . By deleting from , we get a path. Therefore, if we construct using this path instead of , then we would still get a connected graph, apart from possibly which might be an isolated node. Since , it follows that there are a side in and a side in that are consecutive along the path and therefore by Lemma 2.4 belong to a gadget crossing the cut. Similarly, there cannot be just one -side in a component from that is part of every gadget crossing the cut, since constructing the transitions graph with respect to results in the same graph. Considering the -edges crossing the cut and base edges in components from that belong to corresponding gadgets, we have a bipartite graph such that each of its classes (sides of and ) contains at least two vertices and every vertex has degree at least one. Such a bipartite graph has a matching of size two, that is, two vertex-disjoint bases in .
Definition 4.6. Let be a node of and let be a set of gadgets associated with -edges adjacent to . We say that is admissible (with respect to ) if each edge is associated with at most two gadgets in and if is associated with exactly two gadgets in , then their bases in are vertex-disjoint.
Proposition 4.7. Let be a node in and let be an admissible set of gadgets with respect to . Then . Furthermore, if all gadgets in are pure of the same type, then .
Proof. Suppose first that , that is, is a tree. Let denote the -hooking gadgets in and let denote their bases in , where a base may appear with multiplicity in if it belongs to several gadgets in . Let denote the maximum vertex degree in the subgraph of consisting of the base edges in . Then : Firstly, by admissibility a vertex cannot belong to two bases of two gadgets on the same -edge. Secondly, if a vertex (polygon-side) belongs to three bases of gadgets on different -edges, then a polygon-side incident to it must belong to the other nodes (components) of these edges. But that is impossible since a polygon-side has just two incident sides. Now, if all the gadgets in are -pure, then it follows from admissibility and Proposition 4.4 that is a matching, that is, . If the bases in are pairwise near, then by Proposition 4.3 there is an edge in that is incident to all of them. This implies that , because at most bases are incident to each endpoint of that edge. Otherwise, if there is a pair of non-near bases in , then it follows from Lemma 3.2 that they must belong to two gadgets associated with the same -edge. Furthermore, by this lemma every other base in must be near each of these two bases. Therefore, by Proposition 4.3 all the other bases in must form a star which implies that there are at most such bases. Therefore, in this case. If all the gadgets in are -pure, then recall that and therefore . Otherwise, if then .
Let denote the -hooking gadgets in and let denote the maximum vertex-degree is the subgraph of consisting of their corresponding base edges in . Clearly, the same arguments apply to , therefore if all the gadgets in are pure of the same type, then .
It remains to consider the case that not all gadgets are pure of the same type. If there is at least one double gadget, then . Otherwise, if all the gadgets are pure but not of the same type, then . This concludes the case that is a tree.
Suppose now that and let be a spanning tree of . Clearly, contains edges not in . For each such edge choose one of its endpoints and discard from any gadget that contains this endpoint. Denote by the set of remaining gadgets. Note that, as above, every vertex belongs to at most two gadgets in , thus, at most gadgets are discarded. Furthermore, if all the gadgets are pure, then every vertex belongs to at most one gadget in and therefore at most gadgets are discarded. We would like to apply the above arguments to conclude that (and , if all gadgets are pure of the same type). Clearly, is admissible. Note that also satisfies the nearness relations. Indeed, if the deleted edge was a witness of two near bases, then one of them is incident to , thus, the corresponding gadget and base were discarded.
It follows from the discussion above that and therefore . If all the gadgets in are pure of the same type, then every vertex belongs to at most one gadget and therefore at most gadgets are discarded and at most three survive. Thus, in this case.
Proposition 4.8. A connected component contains a cycle if:
(a) there are three pure same-type gadgets associated with three -edges connecting to three distinct components; or
(b) has two distinct neighbors and in , there are two gadgets associated with whose bases in are vertex-disjoint, there are two gadgets associated with whose bases in are vertex-disjoint, and these four gadgets are pure of the same type.
Proof. Suppose that (a) holds. Then by Proposition 4.4 those gadgets have three vertex-disjoint edge bases in . Therefore by Lemma 3.2 these base edges are pairwise near and it follows from Proposition 4.3 that is not a tree.
Suppose now that (b) holds. Considering the four corresponding bases in , it follows from the assumption and Proposition 4.4 that they are pairwise vertex-disjoint. By Lemma 3.2 there is an edge of between each of the two bases that corresponds to and each of the two bases that corresponds to . Therefore, by contracting the four bases we obtain a copy of . Thus, .
Summarizing the properties of . Before proceeding to the proof of the optimal bound, we summarize the main properties of the transitions graph for convenience and future reference. Recall that every node of corresponds to a bipartite graph. Every edge of is associated with at least one ‘gadget’: two pairs of adjacent vertices (‘bases’ of the gadget), one from and the other from . Each such gadget has at least one of the labels . If it has both labels, then we call it ‘double’ and otherwise it is ’pure’. The following summarizes Lemma 3.1, Lemma 3.2, Proposition 4.4 and Proposition 4.5.
satisfies the following properties:
There are no two node-disjoint -edges associated with two gadgets sharing a label.
Consequently, for each label the -edges associated with gadgets of this label form a star or a triangle.
If two gadgets with the same label are associated with two -edges and (), then their bases in are near. If both gadgets are pure, then their bases are vertex-disjoint and therefore are connected by an edge of .
For every partition of the nodes of into two disjoint subsets and such that and there are two gadgets crossing the cut with vertex-disjoint bases in .
The optimal bound
Recall that it is enough to show that . Therefore, we may assume that and in particular . We consider the transitions graph and denote by (resp., ) the subgraph of that consists of -edges associated with -hooking (resp., -hooking) gadgets. Recall that it follows from Lemma 3.1 that each of these subgraphs is either a triangle or a star (ignoring isolated nodes). We proceed by considering the possible cases.
Case 1. At least one of and is a star. Suppose without loss of generality that is a star whose center is . Then is either a triangle or a star.
Subcase 1.1. is a triangle. Since is connected, and share at least one node. There are four possible cases: either is one node of the triangle (see Figure 10(a)), or is not a node of the triangle and there are exactly leaves in that belong to , for (see Figure 10(b)–(Figure 10d)). In the first case, is connected to leaves that do not belong to . For each such leaf we apply Proposition 4.5 on the cut and obtain two -pure gadgets with disjoint bases in . This results in an admissible set of -pure gadgets that satisfies the properties in Proposition 4.7. Therefore, . However, this implies that .
Figure 10. If is a star and is a triangle then either (a) the center of the star belongs to ; or (b)–(d) exactly of its leaves in belong to , for .
Otherwise, suppose that does not belong to (see Figure 10(b)–(Figure 10d)). Then by applying Proposition 4.5 on the cut for each leaf from the leaves in that do not belong to and also for the cut , we again obtain an admissible set of -pure gadgets and conclude that as above.
Subcase 1.2. is a star whose center is . In this case is a star with center and leaves. For a leaf we apply Proposition 4.5 on the cut , and obtain two gadgets with disjoint bases in . By repeating this for each of the leaves, we obtain an admissible set of gadgets that satisfies the properties in Proposition 4.7. Note that these gadgets are not necessarily pure. Therefore, , which is impossible.
Subcase 1.3. is a star with center . Each of the other components is adjacent to , , or both. For each such component we apply Proposition 4.5 on the cut and obtain two gadgets with disjoint bases in . Note that each of these gadgets is either -pure or -pure. Denote by and the number of those gadgets, respectively. Then . Applying Proposition 4.7 on and the subset of those -pure gadgets, we get that . Similarly, we have . Thus we have,
which implies that . Since we assumed that , it remains to consider the case that contains exactly five connected components.
Suppose that and let be the other connected components of apart from and . We may further assume that and that (4) holds with equality, for otherwise we immediately get and we are done. Thus, and therefore (because , for ).
Recall that for every , exactly two of those six gadgets have one base in , the other base in or , and if both gadgets are associated with the same -edge, then their bases in the star-center are disjoint. Observe first that it follows from the first part of Proposition 4.8 that it is impossible to have three gadgets associated with the three edges , since this would imply that . By the second part of Proposition 4.8 it is also impossible that two of these gadgets are over and two others are over , for . Applying the same arguments for , we conclude that, without loss of generality, there are two gadgets over each of and and one gadget over each of and (see Figure 11).
Figure 11. An illustration for Subcase 1.3: , is connected by two -pure gadgets to , by a -pure gadget to , and by a double gadget to . is also connected by two -pure gadgets to and by a -pure gadget to .
By applying Proposition 4.5 on the cut , it follows that there must be another -edge crossing this cut except . Such an edge can only be (see Figure 11). Note that no gadget associated with this edge can be pure. Indeed, if it is -pure, then considering pure gadgets between and each of , and , it follows that by the first part of Proposition 4.8. Similarly, cannot be associated with a -pure gadget. Let and be vertex-disjoint bases in from -pure gadgets associated with , and let be a base in from a -pure gadget associated with . Note that does not share vertices with and by Proposition 4.4, and that there are edges connecting to both of and by Lemma 3.2. Therefore and are not connected by an edge, for otherwise we could contract , and and get a 3-cycle implying .
Consider now the cut . Every gadget that crosses this cut is either a -pure gadget associated with or a double gadget associated with . By Lemma 3.2 the base edge in of such gadgets must be near each of and . It follows from Proposition 4.3(b) that these base edges form a star. However, this contradicts Proposition 4.5 by which there should be two vertex-disjoint base edges in that belong to two gadgets crossing this cut.
Case 2. Both and are triangles. Since is connected, it follows that . Recalling the assumption that , we may assume that the two triangles share exactly one node, denote it by . Let and be the other nodes of and let and be the other nodes of . Note that since no -edge belongs to both and , it follows that every gadget associated with the six edges of is pure. We may also assume that each of the five connected components of is a tree, for otherwise and we are done.
Let be the set of endpoints of base edges in of gadgets that are associated with , for . It follows from Proposition 4.4 that for . By Lemma 3.2, each of the subgraphs of induced by and is connected. Recall that is a tree, hence there is a unique path connecting the subtrees and . Let be a -side that corresponds to a vertex on this path. See Figure 12 for an illustration.
Figure 12. An illustration for Case 2: and are two triangles sharing exactly one node .
Omitting from , we obtain a sequence of -sides. Some of them belong to and some to , as every connected component of contains sides of both polygons and we omitted a side from . Recall that transitions along this sequence between sides that belong to different connected components correspond to -edges. Since there are no transitions between and , it follows that there is a subsequence of consecutive -sides such that each of them belongs to , , , the side before belongs to and the side after belongs to (we may assume that this is the order without loss of generality, since we can reverse the sequence of sides if needed).
We claim that for every , there is a side of that is disjoint from both and . Indeed, suppose that there is no -side that is disjoint from both and . Then, it follows from Lemma 2.4 that and are part of a gadget . Because , all the sides of belong to . Since there is a -pure gadget associated with and its sides are disjoint from those of , it follows from Lemma 2.7 that is not -hooking. Similarly, since there is a -pure gadget associated with it follows that is also not -hooking, a contradiction.
Therefore, for every , there is a -side (in ) such that . Thus, there is a path between and , which avoids , a contradiction. Hence, is not a tree and we are done.
The gap in the proof of the upper bound in [1]
For the proof of the upper-bound in [1] one assumes that there are more than connected components in , where is a huge constant. Using Ramsey theory and Lemma 2.7 it then follows that there are six pairwise side-disjoint -hooking gadgets , , with the following properties (some are implied by the other):
The lines containing the sides form a 6-cap such that the slope of is greater than the slope of for every ;
the sides are pairwise disjoint and lies on , for every ;
and belong to different connected components of for every ;
and belong to different connected components of for every ;
and belong to the same connected component of for every and ;
crosses for every ;
crosses for every and ; and
crosses for every and .
The proof proceeds by a case-analysis resulting in a contradiction in every case. In Case 2, one assumes that for the side does not cross to the left of . Then one considers the four possible subcases depending on whether is the left or right endpoint of and whether is the left or right endpoint of . In Subcase 2.2 is the left endpoint of and is the left endpoint of . The side crosses both and , which partition it into three parts. It is then claimed that if intersects the middle part of (between and ), then cannot cross both and in the wedge determined by and . That is true if crosses between and , as is assumed implicitly by the accompanying figure (see Figure 13a). However, it is possible that crosses between and , and then may cross both and inside the above-mentioned wedge, see Figure 13b and Figure 14.
Figure 13. (a) is implicitly assumed to cross between and . (b) the case that crosses between and is not handled. Figure 13: The gap in the proof of the upper bound in [1].
!A realization of the omitted case in [1] by straight-line segments bbox=0.14,0.35,0.83,0.66
Figure 14. A realization of the omitted case in [1] by straight-line segments.
It seems that the gap in this case-analysis can be resolved by considering seven gadgets instead of six (thus taking a greater constant ). However, since the current proof is simpler and gives a better upper bound, there is not much point in going into those technicalities.
References
- [1]Eyal Ackerman, Balázs Keszegh, and Günter Rote. An almost optimal bound on the number of intersections of two simple polygons. Discrete & Computational Geometry, 68(4):1049–1077, 2022. doi:10.1007/s00454-022-00438-0.DOI
- [2]J. Černý, J. Kára, D. Král’, P. Podbrdský, M. Sotáková, and R. Šámal. On the number of intersections of two polygons. Comment. Math. Univ. Carolinae, 44(2):217–228, 2003. URL: https://cmuc.karlin.mff.cuni.cz/cmuc0302/cmuc0302.htm.
- [3]Michael B. Dillencourt, David M. Mount, and Alan Saalfeld. On the maximum number of intersections of two polyhedra in 2 and 3 dimensions. In Proceedings of the 5th Canadian Conference on Computational Geometry, Waterloo, Ontario, Canada, August 1993, pages 49–54. University of Waterloo, 1993.
- [4]Ju Yong Seo. The maximum number of intersections of two simple polygons with an odd number of sides: A computer-assisted proof of a conjecture of Ackerman, Keszegh and Rote, October 2026. Preprint. doi:10.5281/zenodo.23306693.











