We consider the problem of 2-coloring geometric hypergraphs. Specifically, we show that there is a constant m such that any finite set of points in the plane S ⊂ R 2 can be 2-colored such that every axis-parallel square that contains at least m points from S contains points of both colors. Our proof is constructive, that is, it provides a polynomial-time algorithm for obtaining such a 2-coloring. By affine transformations this result immediately applies also when considering 2-coloring points with respect to homothets of a fixed parallelogram.

EB00000003325K

Available