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)=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).
subject
Last update: July 19, 2013.