We study the problem of conflict-free (CF) coloring of a set of points in the plane, in an online fashion, with respect to halfplanes, nearly-equal axis-parallel rectangles, and congruent disks. As a warm-up exercise, the online CF coloring of points on the line with respect to intervals is also considered. We present randomized algorithms in the oblivious adversary model, where the adversary does not see the colors used. For the problems considered, the algorithms always produce valid CF colorings, and use O(logn) colors with high probability (these bounds are optimal in the worst case). Our randomized online algorithms are considerably simpler than previous algorithms for this problem and use fewer colors.We also present a deterministic algorithm for the CF coloring of points in the plane with respect to nearly-equal axis-parallel rectangles, using O(polylog(n)) colors. This is the first efficient deterministic online CF coloring algorithm for this problem.
展开▼
机译:我们以在线方式研究半平面,几乎相等的轴平行矩形和全等圆盘上平面上的一组点的无冲突(CF)着色问题。作为热身运动,还应考虑线上相对于间隔的点的在线CF着色。我们在遗忘对手模型中提出了随机算法,其中对手看不到所用的颜色。对于所考虑的问题,算法始终会产生有效的CF着色,并以高概率使用 O I>(log n I>)颜色(这些边界在最坏的情况下是最佳的)。对于这个问题,我们的随机在线算法比以前的算法简单得多,并且使用的颜色更少。我们还提出了一种确定性算法,用于使用 O < / I>(polylog( n I>))颜色。这是针对此问题的第一种有效的确定性在线CF着色算法。
展开▼