Conflict-free coloring of points with respect to rectangles and approximation algorithms for discrete independent set

In the conflict-free coloring problem, for a given range space, we want to bound the minimum value F(n) such that every set P of n points can be colored with F(n) colors with the property that every nonempty range contains a unique color. We prove a new upper bound O(n ^0.368) with respect to orthogonal ranges in two dimensions (i.e., axis-parallel rectangles), which is the first improvement over the previous bound O(n ^0.382) by Ajwani, Elbassioni, Govindarajan, and Ray [SPAA'07]. This result leads to an O(n ^1-0.632/2d-2) upper bound with respect to orthogonal ranges (boxes) in dimension d, and also an O(n ^{1-0.632/(2d-3-0.368)}) upper bound with respect to dominance ranges (orthants) in dimension d ≥ 4. We also observe that combinatorial results on conflict-free coloring can be applied to the analysis of approximation algorithms for discrete versions of geometric independent set problems. Here, given a set P of (weighted) points and a set S of ranges, we want to select the largest(-weight) subset Q ⊂ P with the property that every range of S contains at most one point of Q. We obtain, for example, a randomized O(n ^0.368)-approximation algorithm for this problem with respect to orthogonal ranges in the plane.