• Calendar

January 27, Wednesday
12:00 – 13:30

I will begin with presenting some problems from computational and combinatorial geometry. After that I will discuss 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? Similarly, one can reformulate the problem by changing halfplanes to a different family of regions. 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)$. We will see that $f(k)=2k-1$, thus completely solving this question for the case of halfplanes. The above questions are related to problems of battery consumption in sensor networks and some other fields in computational geometry.