Optimal discrepancy for triangles

Abstract

We prove that every $n$-point set in the plane has a two-coloring with discrepancy $O(n^{1/4})$ for all triangles. This improves the previous bound $O(n^{1/4}\sqrt{\log n})$ and matches the classical lower bound.