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?

  • $\begingroup$ Please explain what you mean by saying "triangles that contain the angle $\alpha$". Do you mean "triangles having at least one of their angles' measure $\ge \alpha$ ? $\endgroup$ – Jean Marie Mar 25 at 16:15
  • $\begingroup$ I mean triangles with at least one angle that is exactly $\alpha$. $\endgroup$ – Milo Mar 25 at 23:09

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.

  • $\begingroup$ "Repeated angles in the plane and related problems" by Pach and Sharir can be found here $\endgroup$ – Jean Marie Mar 26 at 2:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.