In a coloring of a set of points P with respect to a family of geometric regions one requires that in every region containing at least two points from P, not all the points are of the same color. Perhaps the most notorious open case is coloring of n points in the plane with respect to axis-parallel rectangles, for which it is known that O(~(n0.368)) colors always suffice, and Ω(logn/~(log2)logn) colors are sometimes necessary.In this note we give a simple proof showing that every set P of n points in the plane can be colored with O(log. n) colors such that every axis-parallel rectangle that contains at least three points from P is non-monochromatic.
展开▼
