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
- 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.
- Subjects :
- Computer Science - Discrete Mathematics
Subjects
Details
- Database :
- arXiv
- Publication Type :
- Report
- Accession number :
- edsarx.2402.07775
- Document Type :
- Working Paper