Conflict-free colorings

By János Pach, Géza Tóth. 2003

66 citations recorded by the source corpus.

A coloring of the elements of a planar point set P is said to be conflict-free if, for every closed disk D whose intersection with P is nonempty, there is a color that occurs in D ∩ P precisely once. We solve a problem of Even, Lotker, Ron, and Smorodinsky by showing that any conflict-free coloring of every set of n points in the plane uses at least c log n colors, for an absolute constant c > 0.Moreover, the same assertion is true for homothetic copies of any convex body D, in place of a disk.

Subfields: Computational Mechanics, Computer Graphics and Computer-Aided Design

View Paper: https://www.semanticscholar.org/paper/524dd64aff8608f9c187a9a5a65bd3f2f73c19d3