论文标题
在两个简单多边形的相交数量上几乎最佳的结合
An almost optimal bound on the number of intersections of two simple polygons
论文作者
论文摘要
假设一般位置的简单$ m $ - gon和简单的$ n $ -gon的边界的交叉点的最大数量是多少？这是组合几何形状中的一个基本问题，如果至少有$ m $和$ n $的一个均为$ m $和$ n $，那么答案很容易，那么每一侧都可以交叉，因此答案为$ mn $。如果恰好一个多边形（例如$ n $ gon）具有奇数的侧面，那么它最多可以与$ m $ -gon的每一侧相交，最多可以$ n-1 $ times;因此，最多有$ MN-M $交叉点。构建符合这些界限的示例并不难。如果$ m $和$ n $都是奇怪的，那么最著名的结构具有$ MN-（m+n）+3 $交叉点，并且猜想这是最大值。但是，最著名的上限仅为$ Mn-（M + \ lceil \ frac {n} {6} \ rceil）$，对于$ m \ ge n $。对于某些常数$ c $，我们证明了$ MN-（m+n）+c $的新上限，除了$ c $的价值外，这是最佳的。
What is the maximum number of intersections of the boundaries of a simple $m$-gon and a simple $n$-gon, assuming general position? This is a basic question in combinatorial geometry, and the answer is easy if at least one of $m$ and $n$ is even: If both $m$ and $n$ are even, then every pair of sides may cross and so the answer is $mn$. If exactly one polygon, say the $n$-gon, has an odd number of sides, it can intersect each side of the $m$-gon at most $n-1$ times; hence there are at most $mn-m$ intersections. It is not hard to construct examples that meet these bounds. If both $m$ and $n$ are odd, the best known construction has $mn-(m+n)+3$ intersections, and it is conjectured that this is the maximum. However, the best known upper bound is only $mn-(m + \lceil \frac{n}{6} \rceil)$, for $m \ge n$. We prove a new upper bound of $mn-(m+n)+C$ for some constant $C$, which is optimal apart from the value of $C$.
