Conflict-Free Coloring

Enter a number of points to begin

Conflict-free coloring simulator

This page simulates an algorithm for conflict-free coloring of points with respect to discs, and lets you test the result yourself.

The problem

Color a set of points in the plane so that every disc containing at least one point also contains a point whose color is unique in that disc. The goal is to use as few colors as possible.

It comes from cellular networks: antennas are the points, colors are frequencies, and a phone anywhere must hear at least one antenna on a frequency no other nearby antenna uses.

The algorithm

Based on Even, Lotker, Ron and Smorodinsky (2003). While points remain:

  1. Build the Delaunay triangulation of the remaining points.
  2. Color that graph so neighbors differ and keep the largest color class: an independent set with at least a sixth of the points.
  3. Give that set the next color and remove it.

Any disc holding two or more remaining points contains a Delaunay edge, so its points never all leave in the same round. That makes the highest color inside any disc unique. Each round removes a constant fraction of the points, so only about log n colors are needed.

Using the simulator

  • Draw points places random points.
  • Generate coloring runs the algorithm.
  • Circle: drag a disc and watch its unique color.
  • Rounds replays the algorithm step by step, and Triangulation shows the graph.