Polychromatic Coloring for Half-Planes

Details Polychromatic Coloring for Half-Planes Polychromatic Coloring for Half-Planes

2010-06-16

arxiv.org/abs/1006.3191v1

Mathematics

Combinatorics

11 pages, 5 figures

Scientific paper

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 $2k-1$ points, also contains at least one point from every color class. We also show that the bound $2k-1$ is best possible. This improves the best previously known lower and upper bounds of $\frac{4}{3}k$ and $4k-1$ respectively. 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 $3k-2$ of the half-planes then $H_p$ contains a half-plane from every color class. This improves the best previously known upper bound of $8k-3$. Another corollary of our first result is a new proof of the existence of small size $\eps$-nets for points in the plane with respect to half-planes.

Affiliated with

Also associated with

No associations

Rating

Polychromatic Coloring for Half-Planes does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Polychromatic Coloring for Half-Planes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Polychromatic Coloring for Half-Planes will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-100460