Use Szemerédi-Trotter to show that $n$ points in the plane determine at most $O(n^{7/3})$ triangles that contain a fixed acute angle $\alpha$.

227 Views Asked by At

I'm doing exercises in Lectures on Discrete Geometry by Jiri Matousek. There's an application of the Szemerédi-Trotter Theorem to a problem of acute-angled triangles:

Fix an acute angle $\alpha$. Use Szemerédi-Trotter to show that $n$ points in the plane determine at most $O(n^{7/3})$ triangles with each triangle having at least one angle $\alpha$.

How do I begin this?

1

There are 1 best solutions below

1
On

Here is an outline. Consider a fixed point $p$ and consider any other point $q$. For any other point $r$ to satisfy $\angle rpq = \alpha$, we have that $r$ must lie on one of two lines (why?). This means that we can count all the occurrences of these triangles that include the point $p$ by the incidents between the $O(n)$ lines ($2$ for every other point $q$) and our set of points. This gives $O(n^{4/3})$ per point $p$ and so $O(n^{7/3})$ altogether.

This bound can actually be improved to $O(n^2 \log n)$ many triangles with angle $\alpha$. See "Repeated angles in the plane and related problems" by Pach and Sharir.