View PDF

Abstract:Let $X$ be a set of $n$ points in the plane, not all on a line. According to the Gallai-Sylvester
theorem, $X$ always spans an \emph{ordinary line}, i.e., one that passes through precisely 2
elements of $X$. Given an integer $c\ge 2,$ a \emph{line} spanned by $X$ is called
\emph{$c$-ordinary} if it passes through at most $c$ points of $X$. A \emph{triangle} spanned by 3
noncollinear points of $X$ is called \emph{$c$-ordinary} if all 3 lines determined by its sides
are \emph{$c$-ordinary}. Motivated by a question of Erd\H os, Fulek \emph{et al.}~\cite{FMN+17}
proved that there exists an absolute constant $c > 2$ such that if $X$ cannot be covered by 2
lines, then it determines at least one $c$-ordinary triangle. Moreover, the number of such
triangles grows at least linearly in $n$. They raised the question whether the true growth rate of
this function is superlinear.
We prove that if $X$ cannot be covered by 2 lines, and no line passes through more than $n-t(n)$
points of $X$, for some function $t(n)\rightarrow\infty,$ then the number of $17$-ordinary
triangles spanned by $X$ is at least constant times $n \cdot t(n)$, i.e., superlinear in $n$. We also
show that the assumption $t(n)\rightarrow\infty$ is necessary. If we further assume that no line
passes through more than $n/2-t(n)$ points of $X$, then the number of $17$-ordinary triangles
grows superquadratically in $n$. This statement does not hold if $t(n)$ is bounded. We close this
paper with some algorithmic results. In particular, we provide a $O(n^{2.372})$ time algorithm for
counting all $c$-ordinary triangles in an $n$-element point set, for any $c<n$.

Submission history

From: Adrian Dumitrescu [view email]
[v1] Fri, 3 Oct 2025 19:06:20 UTC (173 KB)
[v2] Fri, 17 Jul 2026 22:55:11 UTC (174 KB)