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.