论文标题
没有选择空的三角形的引理
No Selection Lemma for Empty Triangles
论文作者
论文摘要
让$ s $是一组$ n $点在飞机上的总位置。第二选择引理指出，对于任何$θ（n^3）$三角形的家族，$ s $跨越了$ s $，存在飞机点的点，其中持续不断。对于$θ（n^{3-α}）$三角形的家族，带有$ 0 \leα\ le 1 $，可能没有超过$θ（n^{3-2α}）$的点。 $ s $的空三角形是一个由$ s $跨越的三角形，不包含其内部$ s $的任何点。巴拉尼（Bárány）猜想，有一个由$ s $跨越的边缘，这是$ s $的超恒定空的三角形的事件。 $ s $的空三角形的数量可能是$ o（n^2）$;在这种情况下，平均而言，$ s $跨越的每个边缘都是恒定数量的空三角形的事件。 Bárány的猜想表明，对于空的三角形，上述上限可能无法固定。在本文中，我们表明，有些令人惊讶的是，上面的上限实际上确实适合空的三角形。具体来说，我们表明，对于任何整数$ n $和实际数字$ 0 \ leqleqα\ leq 1 $，存在一组尺寸$ n $，带有$θ（n^{3-α}）$空的三角形，使得飞机的任何点仅在$ o（n^{3-2α}）$ o（n^{3-2α}）$空的triangles中。
Let $S$ be a set of $n$ points in general position in the plane. The Second Selection Lemma states that for any family of $Θ(n^3)$ triangles spanned by $S$, there exists a point of the plane that lies in a constant fraction of them. For families of $Θ(n^{3-α})$ triangles, with $0\le α\le 1$, there might not be a point in more than $Θ(n^{3-2α})$ of those triangles. An empty triangle of $S$ is a triangle spanned by $S$ not containing any point of $S$ in its interior. Bárány conjectured that there exist an edge spanned by $S$ that is incident to a super constant number of empty triangles of $S$. The number of empty triangles of $S$ might be $O(n^2)$; in such a case, on average, every edge spanned by $S$ is incident to a constant number of empty triangles. The conjecture of Bárány suggests that for the class of empty triangles the above upper bound might not hold. In this paper we show that, somewhat surprisingly, the above upper bound does in fact hold for empty triangles. Specifically, we show that for any integer $n$ and real number $0\leq α\leq 1$ there exists a point set of size $n$ with $Θ(n^{3-α})$ empty triangles such that any point of the plane is only in $O(n^{3-2α})$ empty triangles.
