Online Conflict-Free Coloring for Intervals

@article{citeulike:1082153, abstract = {We consider an online version of the conflict-free coloring of a set of points on the line, where each newly inserted point must be assigned a color upon insertion, and at all times the coloring has to be conflict-free, in the sense that in every interval \$I\$ there is a color that appears exactly once in \$I\$. We present deterministic and randomized algorithms for achieving this goal, and analyze their performance, that is, the maximum number of colors that they need to use, as a function of the number \$n\$ of inserted points. We first show that a natural and simple (deterministic) approach may perform rather poorly, requiring \$\Omega(\sqrt{n})\$ colors in the worst case. We then derive two efficient variants of this simple algorithm. The first is deterministic and uses \$O(\log^2 n)\$ colors, and the second is randomized and uses \$O(\log n)\$ colors with high probability. We also show that the \$O(\log^2 n)\$ bound on the number of colors used by our deterministic algorithm is tight on the worst case. We also analyze the performance of the simplest proposed algorithm when the points are inserted in a random order and present an incomplete analysis that indicates that, with high probability, it uses only \$O(\log n)\$ colors. Finally, we show that in the extension of this problem to two dimensions, where the relevant ranges are disks, \$n\$ colors may be required in the worst case.}, author = {Chen, Ke and Fiat, Amos and Kaplan, Haim and Levy, Meital and Matou\&\#x0161;ek, Jiri and Mossel, Elchanan and Pach, Janos and Sharir, Micha and Smorodinsky, Shakhar and Wagner, Uli and Welzl, Emo }, citeulike-article-id = {1082153}, journal = {SIAM Journal on Computing}, keywords = {algorithm, approximation, coloring, geometry}, number = {5}, pages = {1342--1359}, posted-at = {2007-02-01 15:32:36}, priority = {2}, publisher = {SIAM}, title = {Online Conflict-Free Coloring for Intervals}, url = {http://scitation.aip.org/getabs/servlet/GetabsServlet?prog=normal\&id=SMJCAT000036000005001342000001\&idtype=cvips\&gifs=yes}, volume = {36}, year = {2006} }

TY - JOUR ID - citeulike:1082153 L3 - citeulike-article-id:1082153 TI - Online Conflict-Free Coloring for Intervals JF - SIAM Journal on Computing VL - 36 IS - 5 SP - 1342 EP - 1359 PB - SIAM N2 - We consider an online version of the conflict-free coloring of a set of points on the line, where each newly inserted point must be assigned a color upon insertion, and at all times the coloring has to be conflict-free, in the sense that in every interval $I$ there is a color that appears exactly once in $I$. We present deterministic and randomized algorithms for achieving this goal, and analyze their performance, that is, the maximum number of colors that they need to use, as a function of the number $n$ of inserted points. We first show that a natural and simple (deterministic) approach may perform rather poorly, requiring $\Omega(\sqrt{n})$ colors in the worst case. We then derive two efficient variants of this simple algorithm. The first is deterministic and uses $O(\log^2 n)$ colors, and the second is randomized and uses $O(\log n)$ colors with high probability. We also show that the $O(\log^2 n)$ bound on the number of colors used by our deterministic algorithm is tight on the worst case. We also analyze the performance of the simplest proposed algorithm when the points are inserted in a random order and present an incomplete analysis that indicates that, with high probability, it uses only $O(\log n)$ colors. Finally, we show that in the extension of this problem to two dimensions, where the relevant ranges are disks, $n$ colors may be required in the worst case. KW - algorithm KW - approximation KW - coloring KW - geometry AU - Chen, Ke AU - Fiat, Amos AU - Kaplan, Haim AU - Levy, Meital AU - Matoušek, Jiri AU - Mossel, Elchanan AU - Pach, Janos AU - Sharir, Micha AU - Smorodinsky, Shakhar AU - Wagner, Uli AU - Welzl, Emo PY - 2006/// UR - http://scitation.aip.org/getabs/servlet/GetabsServlet?prog=normal&id=SMJCAT000036000005001342000001&idtype=cvips&gifs=yes ER -