EUVIMEDEUVIMED entdecken
Crossref

Note on the Number of Almost Ordinary Triangles

Adrian Dumitrescu, Janos Pach

The Electronic Journal of Combinatorics · 07.08.2026 · 33 (3)

DOI: 10.37236/14703 ↗

Kurz gefasst

Fachartikel in der Zeitschrift The Electronic Journal of Combinatorics, online erschienen am 07.08.2026. Verfasst von Adrian Dumitrescu und 1 weiteren Autor:innen.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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\ge 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ős, R. Fulek et al. [\emph{Comput. Geom.} \textbf{66} (2017), 28--31] 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

Zitieren

APA

Dumitrescu, A., & Pach, J. (2026). Note on the Number of Almost Ordinary Triangles. The Electronic Journal of Combinatorics, 33(3). https://doi.org/10.37236/14703

Vancouver

Dumitrescu A, Pach J. Note on the Number of Almost Ordinary Triangles. The Electronic Journal of Combinatorics. 2026;33(3). doi:10.37236/14703

BibTeX
@article{Dumitrescu2026,
  author = {Dumitrescu, Adrian and Pach, Janos},
  title = {Note on the Number of Almost Ordinary Triangles},
  journal = {The Electronic Journal of Combinatorics},
  year = {2026},
  volume = {33},
  number = {3},
  doi = {10.37236/14703}
}
Kostenlos starten →