Online Conflict-Free Coloring for Halfplanes, Congruent Disks, and Axis-Parallel Rectangles
We present randomized algorithms for online conflict-free coloring (CF in short) of points in the plane, with respect to halfplanes, congruent disks, and nearly-equal axis-parallel rectangles. In all three cases, the coloring algorithms use O(log n) colors, with high probability. We also present a deterministic algorithm for online CF coloring of points in the plane with respect to nearly-equal axis-parallel rectangles, using O(log(3) n) colors. This is the first efficient (i.e, using polylog(n) colors) deterministic online CF coloring algorithm for this problem.
coloring conflict free coloring online algorithms