Online conflict-free coloring for halfplanes, congruent disks, and axis-parallel rectangles

Abstract

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.