Almost Congruent Triangles
Preprint
Abstract
Almost $50$ years ago Erdős and Purdy asked the following question: Given $n$ points in the plane, how many triangles can be approximate congruent to equilateral triangles? They pointed out that by dividing the points evenly into three small clusters built around the three vertices of a fixed equilateral triangle, one gets at least $\left\lfloor \frac{n}{3} \right\rfloor \cdot \left\lfloor \frac{n+1}{3} \right\rfloor \cdot \left\lfloor \frac{n+2}{3} \right\rfloor$ such approximate copies. In this paper we provide a matching upper bound and thereby answer their question. More generally, for every triangle $T$ we determine the maximum number of approximate congruent triangles to $T$ in a point set of size $n$. Parts of our proof are based on hypergraph Turán theory: for each point set in the plane and a triangle $T$, we construct a $3$-uniform hypergraph $\mathcal{H}=\mathcal{H}(T)$, which contains no hypergraph as a subgraph from a family of forbidden hypergraphs $\mathcal{F}=\mathcal{F}(T)$. Our upper bound on the number of edges of $\mathcal{H}$ will determine the maximum number of triangles that are approximate congruent to $T$.
Keywords
All Related Versions
This publication has 12 references indexed in Scilit:
- Maximum number of almost similar triangles in the planeComputational Geometry, 2022
- Hypergraphs Do JumpCombinatorics, Probability and Computing, 2010
- On 3-Hypergraphs with Forbidden 4-Vertex ConfigurationsSIAM Journal on Discrete Mathematics, 2010
- Flag algebrasThe Journal of Symbolic Logic, 2007
- Research Problems in Discrete Geometry2005
- Classification of three-distance sets in two dimensional Euclidean spaceEuropean Journal of Combinatorics, 2004
- Stability theorems for cancellative hypergraphsJournal of Combinatorial Theory, Series B, 2004
- On the Maximum Number of Equilateral Triangles, IDiscrete & Computational Geometry, 2000
- Hypergraphs do not jumpCombinatorica, 1984
- Three-graphs without two triples whose symmetric difference is contained in a thirdDiscrete Mathematics, 1974