## 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].
*
### 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`)=3`k`-2.
This can be interpreted as coloring point sets in the plane with `k`
colors such that any bottomless rectangle containing at least 3`k`-2
points contains at least one point of each color. We also prove a lower
bound `p`(`k`)>1.67`k`. 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).

subject
Last update: July 19, 2013.