Skip to content
All projects

BGU mini-project, 2025

Conflict-Free Coloring

An interactive simulator that colors points so every disc contains a color appearing exactly once, using only O(log n) colors.

Live demo Source
The simulator with colored points on a dark canvas, a test circle and the control panel
  • Implements a published algorithm (Even, Lotker, Ron and Smorodinsky, 2003) that needs only O(log n) colors.
  • Lets you test the result yourself: draw any circle, replay the rounds, overlay the triangulation.
  • No build step and a single small dependency. Runs entirely in the browser, even offline.

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 inside that disc, and use as few colors as possible.

The problem comes from frequency assignment in cellular networks. The points are antennas and the colors are frequencies: wherever a phone is, it must hear at least one antenna on a frequency that no other antenna in range is using.

How the algorithm works

We implemented the algorithm of Even, Lotker, Ron and Smorodinsky (2003). While points remain:

  1. Build the Delaunay triangulation of the remaining points.
  2. Color that graph so neighbors get different colors, and keep the largest color class. It is an independent set: no two of its points are Delaunay neighbors.
  3. Give that set the next color and remove it.

Why this works: any disc holding two or more of the remaining points contains a Delaunay edge between two of them, so those points never leave in the same round. As a result, the highest color inside any disc appears exactly once.

Rounds mode: earlier colors fade out while the remaining points show their Delaunay graph

Engineering decisions

Greedy coloring instead of four-coloring. The paper four-colors the planar Delaunay graph. We color it greedily in smallest-last order, built with degree buckets so it runs in linear time. A planar graph always has a vertex of degree at most 5, so this uses at most 6 colors: every round removes at least a sixth of the points, and the total stays O(log n).

Edge cases handled explicitly. When every point lies on one line, the triangulation library returns no triangles, so we fall back to the path through the points in order. With fewer than four points left, each one simply gets its own color.

Verify, don’t assume. When you draw a circle, the page finds the highest color inside it and counts how many times it appears. The conflict-free property is checked live on every test instead of being taken on faith.

Replayable rounds. While it runs, the algorithm records the remaining points and their Delaunay edges for every round, so the Rounds tool can step through it with buttons, Play, or the arrow keys.

Colors that never collide. Past the fixed palette, new colors are generated with golden-angle hue steps, so two different color numbers never share a swatch.

Circle mode: a disc drawn on the canvas, with its unique highest color reported in the panel

What we built

  • Canvas rendering of the grid, points, triangulation and circles, with the coloring revealed round by round.
  • Up to 9,801 distinct random points on a 100 by 100 grid.
  • Three tools to explore the result: Circle, Rounds and Triangulation.
  • A point table synced with the canvas: hovering a row highlights its point, and the other way around.
  • A short in-app guide that explains the problem and the algorithm to first-time visitors.

The Delaunay triangulation of all points overlaid on the coloring

Reference

G. Even, Z. Lotker, D. Ron and S. Smorodinsky. Conflict-Free Colorings of Simple Geometric Regions with Applications to Frequency Assignment in Cellular Networks. SIAM Journal on Computing 33(1), 2003.