---
OA_type: closed access
_id: '2428'
abstract:
- lang: eng
  text: 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 several
    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 Ω(√n) colors
    in the worst case. We then modify this approach, to obtain an efficient deterministic
    algorithm that uses a maximum of Θ(log 2 n) colors. Next, we present two randomized
    solutions. The first algorithm requires an expected number of at most O(log 2
    n) colors, and produces a coloring which is valid with high probability, and the
    second one, which is a variant of our efficient deterministic algorithm, requires
    an expected number of at most O(log n log log n) colors but always produces a
    valid coloring. 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. The average-case
    behavior for disks, and cases involving other planar ranges, are still open.
article_processing_charge: No
author:
- first_name: Amos
  full_name: Fiat, Amos
  last_name: Fiat
- first_name: Meital
  full_name: Levy, Meital
  last_name: Levy
- first_name: Jiří
  full_name: Matoušek, Jiří
  last_name: Matoušek
- first_name: Elchanan
  full_name: Pach, Elchanan
  last_name: Pach
- first_name: Micha
  full_name: Sharir, Micha
  last_name: Sharir
- first_name: Shakhar
  full_name: Smorodinsky, Shakhar
  last_name: Smorodinsky
- first_name: Uli
  full_name: Wagner, Uli
  id: 36690CA2-F248-11E8-B48F-1D18A9856A87
  last_name: Wagner
  orcid: 0000-0002-1494-0568
- first_name: Emo
  full_name: Welzl, Emo
  last_name: Welzl
citation:
  ama: 'Fiat A, Levy M, Matoušek J, et al. Online conflict-free coloring for intervals.
    In: <i>Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms</i>.
    SIAM; 2005:545-554. doi:<a href="https://doi.org/10.1137/S0097539704446682">10.1137/S0097539704446682</a>'
  apa: 'Fiat, A., Levy, M., Matoušek, J., Pach, E., Sharir, M., Smorodinsky, S., …
    Welzl, E. (2005). Online conflict-free coloring for intervals. In <i>Proceedings
    of the sixteenth annual ACM-SIAM symposium on Discrete algorithms</i> (pp. 545–554).
    Vancouver, BC, Canada: SIAM. <a href="https://doi.org/10.1137/S0097539704446682">https://doi.org/10.1137/S0097539704446682</a>'
  chicago: Fiat, Amos, Meital Levy, Jiří Matoušek, Elchanan Pach, Micha Sharir, Shakhar
    Smorodinsky, Uli Wagner, and Emo Welzl. “Online Conflict-Free Coloring for Intervals.”
    In <i>Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms</i>,
    545–54. SIAM, 2005. <a href="https://doi.org/10.1137/S0097539704446682">https://doi.org/10.1137/S0097539704446682</a>.
  ieee: A. Fiat <i>et al.</i>, “Online conflict-free coloring for intervals,” in <i>Proceedings
    of the sixteenth annual ACM-SIAM symposium on Discrete algorithms</i>, Vancouver,
    BC, Canada, 2005, pp. 545–554.
  ista: 'Fiat A, Levy M, Matoušek J, Pach E, Sharir M, Smorodinsky S, Wagner U, Welzl
    E. 2005. Online conflict-free coloring for intervals. Proceedings of the sixteenth
    annual ACM-SIAM symposium on Discrete algorithms. SODA: Symposium on Discrete
    Algorithms, 545–554.'
  mla: Fiat, Amos, et al. “Online Conflict-Free Coloring for Intervals.” <i>Proceedings
    of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms</i>, SIAM, 2005,
    pp. 545–54, doi:<a href="https://doi.org/10.1137/S0097539704446682">10.1137/S0097539704446682</a>.
  short: A. Fiat, M. Levy, J. Matoušek, E. Pach, M. Sharir, S. Smorodinsky, U. Wagner,
    E. Welzl, in:, Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete
    Algorithms, SIAM, 2005, pp. 545–554.
conference:
  end_date: 2005-01-25
  location: Vancouver, BC, Canada
  name: 'SODA: Symposium on Discrete Algorithms'
  start_date: 2005-01-23
date_created: 2018-12-11T11:57:36Z
date_published: 2005-01-01T00:00:00Z
date_updated: 2026-08-07T08:37:46Z
day: '01'
doi: 10.1137/S0097539704446682
extern: '1'
language:
- iso: eng
month: '01'
oa_version: None
page: 545 - 554
publication: Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms
publication_identifier:
  isbn:
  - '9780898715859'
publication_status: published
publisher: SIAM
publist_id: '4496'
status: public
title: Online conflict-free coloring for intervals
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
year: '2005'
...