2025/10/03 by Adrian Dumitrescu, János Pach, Dumitrescu, Adrian +1
Mathematics · #History and Theory of Mathematics #Mathematical Dynamics and Fractals #Mathematics and Applications #cs.CG #cs.DM #math.CO
paper · pdf · doi:10.48550/arxiv.2510.03445
openalex publication_date 2025/10/03 · openalex created_date 2025/10/09 · openalex updated_date 2026/07/28
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 ordinary line, i.e., one that passes through precisely 2 elements of X. Given an integer c≥ 2, a line spanned by X is called c-ordinary if it passes through at most c points of X. A triangle spanned by 3 noncollinear points of X is called c-ordinary if all 3 lines determined by its sides are c-ordinary. Motivated by a question of Erd\H os, Fulek et al.~\citeFMN+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)→∞, then the number of 17-ordinary triangles spanned by X is at least constant times n ⋅ t(n), i.e., superlinear in n. We also show that the assumption t(n)→∞ 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(n2.372) time algorithm for counting all c-ordinary triangles in an n-element point set, for any c