Conflict-free coloring of points and simple regions in the plane Academic Article uri icon


  • Abstract 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 (ie, 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.

publication date

  • January 1, 2005