## Jean Cardinal, Nathann Cohen, Sébastien Collette, Michael Hoffmann,
Stefan Langerman, and Günter Rote:

# Coloring dynamic point sets on a line

*to appear in: Abstracts of the 28th European Workshop on Computational
Geometry (EuroCG'12), Assisi, Italy, March 2012, 4 pages, Editor: Walter
Didimo and Giuseppe Liotta.
*
### Abstract

We consider a coloring problem on dynamic, one-dimensional point sets: points
appearing and disappearing on a line at given times. We wish to color them
with `k` colors so that at any time, any sequence of `p(k)`
consecutive points, for some function `p`, contains at least one point
of each color.
No such function `p(k)` exists in general. However, in the restricted
case in which points only appear but never disappear, we give a coloring
algorithm guaranteeing the property at any time with `p(k) = 8k - 5`.
This can be interpreted as coloring point sets in the plane with `k`
colors such that any bottomless rectangle containing at least `8k - 5`
points contains at least one point of each color. Pach and Tóth (2005)
proved that such colorings do not always exist in the case of general
axis-aligned rectangles. Our result also complements recent contributions from
Keszegh and Pálvölgyi (2011).

Last update: February 1, 2012.