Back to Search Start Over

Growth Rate of the Number of Empty Triangles in the Plane

Growth Rate of the Number of Empty Triangles in the Plane

Authors :
Bhattacharya, Bhaswar B.
Das, Sandip
Islam, Sk Samim
Sen, Saumya
Publication Year :
2024

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\'edi problem.

Details

Database :
arXiv
Publication Type :
Report
Accession number :
edsarx.2402.07775
Document Type :
Working Paper