TY - GEN

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

AU - Chan, Timothy M.

PY - 2012

Y1 - 2012

N2 - 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.

AB - 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.

KW - Approximation algorithms

KW - Combinatorial geometry

KW - Conflict-free coloring

KW - Independent set

KW - Range spaces

UR - http://www.scopus.com/inward/record.url?scp=84863906403&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84863906403&partnerID=8YFLogxK

U2 - 10.1145/2261250.2261293

DO - 10.1145/2261250.2261293

M3 - Conference contribution

AN - SCOPUS:84863906403

SN - 9781450312998

T3 - Proceedings of the Annual Symposium on Computational Geometry

SP - 293

EP - 302

BT - Proceedings of the 28th Annual Symposuim on Computational Geometry, SCG 2012

T2 - 28th Annual Symposuim on Computational Geometry, SCG 2012

Y2 - 17 June 2012 through 20 June 2012

ER -