Abstract: We study problems of the following type:
Is there a constant $f=f(k)$ such that any finite set of points in the plane
can be colored with $k$ colors so that any halfplane that contains
at least $f$ points, also contains a point from every color class?
(As a warm-up exercise you can think of the case $k=2$)
If $f(k)$ exists, what is the exact or asymptotic value of $f(k)$ (as
a function of $k$ only)?
Similarly, one can reformulate the problem by changing halfplanes to
a different family of regions. When the family is the set of all translates of
some fixed convex set in the plane, the above question is strongly related to
a famous conjecture of Janos Pach and Laslo Fejes Toth. from the 80's.
For halfplanes, Pach and  G. Toth proved that $f(k)=O(k^2)$. This bound
was later improved by Aloupis et al. to $f(k)=O(k)$.
As a preliminary result, we show that $f(k)=2k-1$, thus completely solving
this question for the case of halfplanes.
The above questions are also related to the theory of Epsilon-Nets for
hypergraphs and to problems of battery consumption in sensor networks.

Joint work with Shakhar Smorodinsky.