Coloring points with respect to squares (Q1688853)

Let \(S\) be any set of points of a plane \(\mathbb{R}^2\) and suppose that we color points of \(S\) with two colors. The authors show that there exists a constant \(m<215\) such that if any (open or closed) parallelogram \(P\) of \(\mathbb{R}^2\) contains at least \(m\) points of \(S\), then there exists a 2-coloring of \(S\) such that \(P\) contains points of both colors. The proof is constructive and provides a polynomial time algorithm for a desired 2-coloring. It is also shown that with this method one can prove a similar result for triangles. In the introduction the connection to geometric hypergraphs is presented which covers above mention model.