Ajwani, DeepakDeepakAjwaniElbassioni, KhaledKhaledElbassioniGovindarajan, SathishSathishGovindarajanRay, SaurabhSaurabhRay2019-04-102019-04-102012 Sprin2012-04-28Discrete and Computational Geometry0179-5376http://hdl.handle.net/10197/9896Given a set of points P ⊆ ℝ 2, a conflict-free coloring of P w. r. t. rectangle ranges is an assignment of colors to points of P, such that each nonempty 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 base stations (points) such that within any range (for instance, rectangle), there is no interference. We show that any set of n points in ℝ 2 can be conflict-free colored with O(n β*+o(1)) colors in expected polynomial time, where β∗=3−5√2<0.382.enThis is a post-peer-review, pre-copyedit version of an article published in Discrete and Computational Geometry. The final authenticated version is available online at: http://dx.doi.org/10.1007/s00454-012-9425-5Frequency assignment in wireless networksConflict-free coloringAxis-parallel rectanglesBoundary setsMonotone sequencesJournal Article481395210.1007/s00454-012-9425-52019-04-01https://creativecommons.org/licenses/by-nc-nd/3.0/ie/