Many empty triangles have a common edge (Q2391838): Difference between revisions

Given a finite point set \(X\) in the plane, the degree of the pair \(\{x,y\} \subset X\) is the number of empty triangles \(t=\{x,y,z\}\), where empty means \(t\cap X = \{x,y,z\}\). Define \(\text{deg}(X)\) as the maximal degree of a pair in \(X\). The main result is that if \(X\) is a random sample of \(n\) independent and uniform points from a fixed convex body, then \(\text{deg}(X) \geq \frac{cn}{\ln(n)}\) in expectation.