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

Coloring dynamic point sets on a line

In: Abstracts of the 28th European Workshop on Computational Geometry (EuroCG'12), Assisi, Italy, March 2012, pp. 209–212, Editors: Walter Didimo and Giuseppe Liotta.

2. Andrei Asinowski, Jean Cardinal, Nathann Cohen, Sébastien Collette, Thomas Hackl, Michael Hoffmann, Kolja Knauer, Stefan Langerman, Michal Lasoń, Piotr Micek, Günter Rote, and Torsten Ueckerdt:

Coloring hypergraphs induced by dynamic point sets and bottomless rectangles

to appear in: Algorithms and Data Structures Symposium-WADS 2013, August 2013, Editors: Frank Dehne, Jörg-Rüdiger Sack, and Roberto Solis-Oba, Lecture Notes in Computer Science, Springer-Verlag, 2013. arXiv:1302.2426 [cs.CG].


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)=3k-2. This can be interpreted as coloring point sets in the plane with k colors such that any bottomless rectangle containing at least 3k-2 points contains at least one point of each color. We also prove a lower bound p(k)>1.67k. Chen, Pach, Szegedy, and Tardos (2009) proved that such colorings do not always exist in the case of general axis-aligned rectangles. Our result also complements recent contributions of Keszegh and Pálvölgyi on cover-decomposability of octants (2011,2012).

  slides of a talk in Prague (July 2012)   pdf file
subject Last update: July 19, 2013.