Growth Rate of the Number of Empty Triangles in the Plane

Abstract

Given a set $P$ of $n$ points in the plane, in general position, denote by $N_{\Delta }(P)$ the number of empty triangles with vertices in $P$. In this paper we investigate by how much $N_{\Delta }(P)$ changes if a point $x$ is removed from $P$. By constructing a graph $G_P(x)$ based on the arrangement of the empty triangles incident on $x$, we transform this geometric problem to the problem of counting triangles in the graph $G_P(x)$. We study properties of the graph $G_P(x)$ and, in particular, show that it is kite-free. This relates the growth rate of the number of empty triangles to the famous Ruzsa-Szemerédi problem.