How to play a coloring game against a color-blind adversary
How to play a coloring game against a color-blind adversary
复制标题
DOI：
10.1145/1137856.1137865
复制
发表时间：
2006-06
期刊：
影响因子：
--
通讯作者：
Ke Chen
中科院分区：
文献类型：
--
作者：
Ke Chen
我们研究了一组点在平面上的无冲突（CF）着色问题，在一个在线的方式，相对于半平面，几乎相等的轴平行矩形，全等磁盘。作为热身练习，还考虑了线上的点相对于间隔的在线CF着色。我们提出了随机算法在不经意的对手模型，对手没有看到使用的颜色。对于所考虑的问题，算法总是产生有效的CF着色，并使用O（logn）的颜色具有高概率（这些界限是最佳的最坏情况下）。我们的随机在线算法是相当简单的，比以前的算法为这个问题，使用较少的colors.We还提出了一个确定性算法的CF染色的点在平面上的几乎相等的轴平行的矩形，使用O（polylog（n））的颜色。这是第一个有效的确定性在线CF着色算法为这个问题。
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.