Quasi‐random 2‐ colorings of point sets
József Beck · Random Structures and Algorithms · 1991
Abstract Given an arbitrary set of N points on the plane, one can two‐color the points red and blue in such a way that the difference of the numbers of red and blue points in any half‐plane has absolute value less than N1/4(log N)4. This is essentially best possible.