No selection lemma for empty triangles

Abstract

Abstract Let P be a set of n points in general position in the plane. The Second Selection Lemma states that for any family of $$\Theta(n^3)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>Θ</mml:mi> <mml:mo>(</mml:mo> <mml:msup> <mml:mi>n</mml:mi> <mml:mn>3</mml:mn> </mml:msup> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> triangles spanned by P , there exists a point of the plane that lies in a constant fraction of them. For families of $$\Theta(n^{3-\alpha})$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>Θ</mml:mi> <mml:mo>(</mml:mo> <mml:msup> <mml:mi>n</mml:mi> <mml:mrow> <mml:mn>3</mml:mn> <mml:mo>-</mml:mo> <mml:mi>α</mml:mi> </mml:mrow> </mml:msup> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> triangles, with $$0\le \alpha \le 1$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>0</mml:mn> <mml:mo>≤</mml:mo> <mml:mi>α</mml:mi> <mml:mo>≤</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:math> , there might not be a point in more than $$\Theta(n^{3-2\alpha})$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>Θ</mml:mi> <mml:mo>(</mml:mo> <mml:msup> <mml:mi>n</mml:mi> <mml:mrow> <mml:mn>3</mml:mn> <mml:mo>-</mml:mo> <mml:mn>2</mml:mn> <mml:mi>α</mml:mi> </mml:mrow> </mml:msup> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> of those triangles. An empty triangle of P is a triangle spanned by P not containing any point of P in its interior. Bárány conjectured that there exists an edge spanned by P that is incident to a super-constant number of empty triangles of P . The number of empty triangles of P might be as low as $$\Theta(n^2)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>Θ</mml:mi> <mml:mo>(</mml:mo> <mml:msup> <mml:mi>n</mml:mi> <mml:mn>2</mml:mn> </mml:msup> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> ; in such a case, on average, every edge spanned by P 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 \alpha \leq 1$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>0</mml:mn> <mml:mo>≤</mml:mo> <mml:mi>α</mml:mi> <mml:mo>≤</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:math> there exists a point set of size n with $$\Theta(n^{3-\alpha})$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>Θ</mml:mi> <mml:mo>(</mml:mo> <mml:msup> <mml:mi>n</mml:mi> <mml:mrow> <mml:mn>3</mml:mn> <mml:mo>-</mml:mo> <mml:mi>α</mml:mi> </mml:mrow> </mml:msup> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> empty triangles such that any point of the plane is only in $$O(n^{3-2\alpha})$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:msup> <mml:mi>n</mml:mi> <mml:mrow> <mml:mn>3</mml:mn> <mml:mo>-</mml:mo> <mml:mn>2</mml:mn> <mml:mi>α</mml:mi> </mml:mrow> </mml:msup> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> empty triangles.

Locations

• Acta Mathematica Academiae Scientiarum Hungaricae - View - PDF