

This
problem
was
posted
to
sci.math
on
4
Oct
1998
by
Norman
Grégoire
(normand@contact.net)
Here
is
a
problem
I'd
like
to
prove,
but
I
don't
know
how
to
proceed
: We
have
a
set
H
of
n
halfplanes
(n>3),
covering
R^{2}. 
I spent some fruitless time trying to work with configurations of halfplanes and the patterns made by their boundary lines, but there were messy special cases where boundary lines were parallel or concurrent. Then I belatedly noticed:
Observation: If we have a set of halfplanes covering the plane, when can we discard one as being redundant? When all its points are covered by other halfplanes. So, if a halfplane h can't be discarded as redundant, there must be at least one point in R^{2} which is only covered by h.
Let H = {h_{1}, h_{2}, ..., h_{n}} be a set of n>3 halfplanes which cover R^{2}. Assume no proper subset of H covers R^{2}. We therefore have a set of points P = {p_{1}, p_{2}, ... p_{n}}, each p_{k} covered only by the halfplane h_{k}.
Lemma: If we have a halfplane h and a finite set S of points which lie entirely outside (resp. inside) h, then all points within the convex hull of S lie entirely outside (resp. inside) h.
No three points in P can be colinear  if p_{b} lies on the line segment joining p_{a} and p_{c} (i.e. on the convex hull of the set { p_{a}, p_{c} } then by the lemma, since p_{a} & p_{c} lie outside the halfplane h_{b}, all points on the line segment, including p_{b}, lie outside h_{b}, but this contradicts p_{b} lies in h_{b}. Similarly, no point lies in the triangle bound by the another 3  the interior of the triangle lies outside the interior point's halfplane, implying the interior point also lies outside its halfplane. The only configuration not excluded by this pattern is for the points to be the vertices of a convex polygon, but in this case, since n>3, there must be two nonadjacent vertices p_{a} and p_{b}. The diagonal p_{a}p_{b} intersects the convex hull of the remaining points P' at some point x. Now, x lies outside h_{a} (resp. h_{b}) since it lies on the convex hull of P', each point of which lies outside h_{a} (resp. h_{b}). Similarly, for each of the remaining points p_{k} in P', x lies outside h_{k} since x lies on the convex hull of {p_{a}, p_{b}}, each point of which lies outside h_{k}. So x doesn't lie in any of the halfplanes in H which collectively cover R^{2}, therefore no such set P exists, therefore the assumption that no proper subset of H covers R^{2} is false  some proper subset H' of H covers R^{2}. By repeating the argument with H', some subset of n<=3 halfplanes in H is sufficient to cover R^{2}.
The problem can be generalised to d dimensions as:
We have a set H of n halfspaces (n>d+1), covering R^{n}.
Prove that some subset of d+1 halfspaces of H is enough to cover R^{n}.
by an analogous proof to the one above by using Radon's Theorem:
Any set of d+2 points in R^{d} can always be partitioned in two subsets V1 and V2 such that the convex hulls of V1 and V2 intersect.
Radon's theorem applies to any set of n>d+1 points in R^{d}; adding extra points to the set can only create larger convex hulls.
Let H = {h_{1}, ..., h_{n}} be a set of n>d+1 halfspaces which covers R^{n}. Assume no proper subset of H covers R^{n}. We therefore have a set of points P = {p_{1}, p_{2}, ... p_{n}}, each p_{k} covered only by the halfspace h_{k}. Since n>d+1, P can be partitioned into two subsets V1 & V2 whose convex hulls intersect at some point x which. For each p_{i} in V1, x isn't covered by corresponding h_{i} since x lies within the convex hull of V2, each point of which lies outside the halfspace h_{i}; similarly for each p_{j} in V2. So x doesn't lie in any of the halfspaces of H which by definition covers R^{n}, hence no such set P exists, hence the assumption that no proper subset of H covers R^{n} is false  some proper subset H' of H covers R^{n}. By repeating the argument with H', some subset of n<=d+1 halfspaces in H is sufficient to cover R^{n}.


