---
res:
bibo_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 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.@eng
bibo_authorlist:
- foaf_Person:
foaf_givenName: Amos
foaf_name: Fiat, Amos
foaf_surname: Fiat
- foaf_Person:
foaf_givenName: Meital
foaf_name: Levy, Meital B
foaf_surname: Levy
- foaf_Person:
foaf_givenName: Jiří
foaf_name: Matoušek, Jiří
foaf_surname: Matoušek
- foaf_Person:
foaf_givenName: Elchanan
foaf_name: Pach, Elchanan M
foaf_surname: Pach
- foaf_Person:
foaf_givenName: Micha
foaf_name: Sharir, Micha
foaf_surname: Sharir
- foaf_Person:
foaf_givenName: Shakhar
foaf_name: Smorodinsky, Shakhar
foaf_surname: Smorodinsky
- foaf_Person:
foaf_givenName: Uli
foaf_name: Uli Wagner
foaf_surname: Wagner
foaf_workInfoHomepage: http://www.librecat.org/personId=36690CA2-F248-11E8-B48F-1D18A9856A87
orcid: 0000-0002-1494-0568
- foaf_Person:
foaf_givenName: Emo
foaf_name: Welzl, Emo
foaf_surname: Welzl
bibo_doi: 10.1137/S0097539704446682
dct_date: 2005^xs_gYear
dct_publisher: SIAM@
dct_title: Online conflict-free coloring for intervals@
...