Conflict-free coloring of points with respect to rectangles and approximation algorithms for discrete independent set
Timothy M. Chan · 2012
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(n0.368) with respect to orthogonal ranges in two dimensions (i.e., axis-parallel rectangles), which is the first improvement over the previous bound O(n0.382) by Ajwani, Elbassioni, Govindarajan, and Ray [SPAA'07]. This result leads to an O(n1-0.632/2d-2) upper bound with respect to orthogonal ranges (boxes) in dimension d, and also an O(n1-0.632/(2d-3-0.368)) upper bound with respect to dominance ranges (orthants) in dimension d ≥ 4.