Polychromatic coloring for half-planes Academic Article uri icon


  • Abstract We prove that for every integer k, every finite set of points in the plane can be k- colored so that every half-plane that contains at least 2 k− 1 points, also contains at least one point from every color class. We also show that the bound 2 k− 1 is best possible. This improves the best previously known lower and upper bounds of 43k and 4 k− 1 respectively. As a corollary, we also show that every finite set of half-planes can be k colored so that if a point p belongs to a subset H p of at least 4 k− 3 of the half-planes then H p contains a half- plane from every color class. This improves the best previously known upper bound of 8 k− 3. Another corollary of our first result is a new proof of the existence of small size ε-nets for points in the plane with respect to half-planes.

publication date

  • January 1, 2012