The maximum number of right triangles formed by $n$ points in the plane

asymptoticscombinatorial-geometrycombinatoricsgeometry

Say we are given $n$ distinct points in the plane. Let $T(n)$ be the maximum number of right triangles one can form by choosing $3$ distinct points from these $n$, where the maximum is taken over all such arrangements. One can prove asymptotic bounds
$$c_1 n^2 \log n \leq T(n) \leq c_2 n^{5/2}.$$
The lower bound comes from considering $n$ points arranged in a $\sqrt{n} \times \sqrt{n}$ grid. The upper bound can be shown as follows: every point either (i) lies on a line with at least $2\sqrt{n}$ points, or (ii) does not lie on such a line. We can cover the points falling into case (i) by $\sqrt{n}$ lines. Given any two points $p_1, p_2$ among the $n$, and one of these lines $L$, at most two of the points on $L$ form a right angle with respect to $p_1, p_2$, so there are at most $2n^2$ right triangles with their right angle on $L$, and so at most $2n^{5/2}$ triangles with a right angle at one of the points from case (i). Also, given a point $p$ falling into case (ii) and a second point $q$, at most $2\sqrt{n}$ points form a triangle with $p$ and $q$ with a right angle at $p$ (since these points all lie on the same line containing $p$), so there are at most $2n^{5/2}$ triangles with a right angle at a point from case (ii).

My question is: can either of these bounds be improved? I would guess the lower bound is close to the right order of magnitude.

Best Answer

The upper bound is also $O(n^2 \log n)$.

This is proved by Pach and Shapir in "Repeated Angles in the Plane and Related Problems", https://doi.org/10.1016/0097-3165(92)90094-B. The proof actually generalizes to any angle, not just a right angle, except it's more complicated in the general case.

Section 2 of the paper gives the proof in the right angle case, but it's several pages long, so I'm not going to quote it here. The essence of the proof is that for each direction $\theta$, we

  • look at lines parallel to $\theta$ that contain at least $2$ points of the set, letting $a_1^\theta, a_2^\theta, \dots, a_k^\theta$ be the counts of points on these lines;
  • look at lines perpendicular to $\theta$ that contain at least $2$ points of the set, lettting $b_1^\theta, b_2^\theta, \dots, b_\ell^\theta$ be the counts of points on these lines;
  • bound the number of right triangles with one side parallel and one side perpendicular to $\theta$ in terms of $a_1^\theta, \dots, a_k^\theta$ and $b_1^\theta, \dots, b_\ell^\theta$.

Then we sum over all $O(n^2)$ directions that matter, and do some work with inequalities.

Related Question