2015/12/07 by Ackerman, Eyal, Keszegh, Balázs, Vizer, Máté · 1 citation
#52C15 (05C15) #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1512.01953
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 ⊂ \mathbb R2 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.