Conflict-free coloring of points and simple regions in the plane

Sariel Har-Peled, Shakhar Smorodinsky

Research output: Contribution to journalArticlepeer-review


We study conflict-free colorings, where the underlying set systems arise in geometry. Our main result is a general framework for conflict-free coloring of regions with low union complexity. A coloring of regions is conflict-free if for any covered point in the plane, there exists a region that covers it with a unique color (i.e., no other region covering this point has the same color). For example, we show that we can conflict-free color any family of n pseudo-discs with O(log n) colors.

Original languageEnglish (US)
Pages (from-to)47-70
Number of pages24
JournalDiscrete and Computational Geometry
Issue number1
StatePublished - Jul 2005

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 of points and simple regions in the plane'. Together they form a unique fingerprint.

Cite this