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

  slides of a talk in Prague (July 2012) with improved results
other papers about this subject
Last update: February 1, 2012.