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.
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.