Tight online conflict-free coloring of intervals

Document Type : Article

Author

Department of Computer Engineering, Sharif University of Technology, Tehran, Iran

10.24200/sci.2020.54600.3826

Abstract

‎We ‎revisit the problem of online conflict-free coloring of intervals on a line‎, ‎where each newly inserted interval must be assigned a color upon insertion such that the coloring remains conflict-free‎, ‎i.e‎. ‎for each point $p$ in the union of the current intervals‎, ‎there must be an interval $I$ with a unique color among all intervals covering $p$‎. ‎To best of our knowledge, the ‎best-‎known ‎algorithm ‎uses‎ $O(\log^3 n )$ ‎colors, where $n$ is the number of current intervals‎. ‎We‎ present a simple greedy algorithm that uses only $O(\log n)$ colors. Therefore, we settle down the open problem raised in \cite{ars1‎4‎}.

Keywords


References    1. Even, G., Lotker, Z., Ron, D., and Smorodinsky, S.    Conict-freee colorings of simple geometric regions    with applications to frequency assignment in cellular    networks", SIAM J. Comput., 33(1), pp. 94{136    (2003).    2. Har-Peled, S. and Smorodinsky S. Conict-free coloring    of points and simple regions in the plane", Discr.    Comput. Geom., 34(1), pp. 47{70 (2005).    3. Ashok, P., Dudeja, A., Kolay, S., and Saurabh, S.    Exact and _xed parameter tractable algorithms for    max-conict-free coloring in hypergraphs", SIAM J.    Discrete Math., 32(2), pp. 1189{1208 (2018).    4. Cheilaris, P., Gargano, L., Rescigno, A.A., and    Smorodinsky, S. Strong conict-free coloring for intervals",    Algorithmica, 70(4), pp. 732{749 (2014).    5. Cui, Z. and Hu, Z. On variants of conict-free-coloring    for hypergraphs", Discrete Applied Mathematics, 220,    pp. 46{54 (2017).    6. Fekete, S.P. and Keldenich, P. Conict-free coloring    of intersection graphs", International Journal of Computational    Geometry and Applications, 28(3), pp. 289{    307 (2018).    7. Gargano, L. and Rescigno, A.A. Complexity of    conict-free colorings of graphs", Theor. Comput. Sci.,    566, pp. 39{49 (2015).    8. Keller, C. and Smorodinsky, S. Conict-free coloring    of intersection graphs of geometric objects", In Proc.    SODA, pp. 2397{2411 (2018).    9. Reddy, I.V. Parameterized algorithms for conict-free    colorings of graphs", Theoretical Computer Science,    745, pp. 53{62 (2018).    10. Chen, K., Fiat, A., Kaplan, H., Levy, M., Matousek,    J., Mossel, E., Pach, J., Sharir, M., Smorodinsky,    S., Wagner, U., and Welzl, E. Online conict-free    coloring for intervals", SIAM J. Comput., 36(5), pp.    1342{1359 (2007).    11. Pach, J. and Toth, G. Conict-free colorings", Discrete    and Computational Geometry, The Goodman-    Pollack Festschrift, B. Aronov, S. Basu, J. Pach and    M. Sharir, Editors, Springer Verlag, Heidelberg, pp.    665{671 (2003).    12. Bar-Noy, A., Cheilaris, P., and Smorodinsky, S.    Conict-free coloring for intervals: from o_ine to    online", In Proc. ACM Sympos. on Parallelism Algorithms    Architectures, pp. 128{137 (2006).    13. Abam, M.A., Rezaei Seraji, M.J., and Shadravan, M.    Online conict-free coloring of intervals", journal of    scientia iranica, Journal of Scientia Iranica, 21(6), pp.    2138{2141 (2014).    14. De Berg, M. and Markovic, A. Dynamic conict-free    colorings in the plane", Comput. Geom., 78, pp. 61{73    (2019).    15. De Berg, M., Leijsen, T., Markovic, A., van Renssen,    A., Roelo_zen, M., and Woeginger, G.J. Fullydynamic    and kinetic conict-free coloring of intervals    with respect to points", Int. J. Comput. Geometry    Appl., 29(1), pp. 49{72 (2019).