Ajwani, DeepakDeepakAjwaniElbassioni, KhaledKhaledElbassioniGovindarajan, SathishSathishGovindarajanRay, SaurabhSaurabhRay2019-04-112019-04-112007 ACM2007-06-11159593667X9781595936677http://hdl.handle.net/10197/9905The 19th ACM Symposium on Parallelism in Algorithms and Architectures, San Diego, California, 9-11 June 2007Given a set of points P ⊆ R 2 , a conflict-free coloring of P w.r.t. rectangle ranges is an assignment of colors to points of P, such that each non-empty axis-parallel rectangle T in the plane contains a point whose color is distinct from all other points in P ∩ T. This notion has been the subject of recent interest, and is motivated by frequency assignment in wireless cellular networks: one naturally would like to minimize the number of frequencies (colors) assigned to bases stations (points), such that within any range (for instance, rectangle), there is no interference. We show that any set of n points in R 2 can be conflict-free colored with O˜(n β+ ) colors in expected polynomial time, for any arbitrarily small > 0 and β = 3− √ 5 2 < 0.382. This improves upon the previously known bound of O( p n log log n/ log n).en© ACM, 2007. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in SPAA '07 Proceedings of the nineteenth annual ACM symposium on Parallel algorithms and architectures (2007) http://doi.acm.org/10.1145/10.1145/1248377.1248406Frequency assignment in wireless networksConflict-free coloringAxis-parallel rectanglesDominating setsMonotone sequencesConference Publication10.1145/1248377.12484062019-04-01https://creativecommons.org/licenses/by-nc-nd/3.0/ie/