Conflict-free coloring for rectangle ranges using O(n .382) colors

Deepak Ajwani, Khaled Elbassioni, Sathish Govindarajan, Saurabh Ray

Research output: Contribution to journalArticlepeer-review


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

Original languageEnglish (US)
Pages (from-to)39-52
Number of pages14
JournalDiscrete and Computational Geometry
Issue number1
StatePublished - Jul 2012


  • Axis-parallel rectangles
  • Boundary sets
  • Conflict-free coloring
  • Frequency assignment in wireless networks
  • Monotone sequences

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics


Dive into the research topics of 'Conflict-free coloring for rectangle ranges using O(n .382) colors'. Together they form a unique fingerprint.

Cite this