From: rusin@vesuvius.math.niu.edu (Dave Rusin)
Newsgroups: sci.math
Subject: Re: Help needed on proving that 3 half-planes are enough
Date: 12 Oct 1998 20:07:24 GMT

Normand Grégoire <normand@contact.net> wrote:

>We have a set P of n half-planes (n>3), covering R2.  Prove that some subset
>of three half-planes of P is enough to cover R2.

It took me longer to devise a proof than I thought it would.


Let us say a set of half-spaces _covers_ if its union is all of  R^2.
Then what we wish to prove is

Theorem: In every finite set S = {H_i, i=1..n}  of half-spaces of  R^2 which
covers, there is a subset of at most three of these half-spaces which covers.

Proof: By induction on  n. If  n <=3, we are done, so we assume  n>= 4.

For each  H  in  S, let  T = S - {H}. If  T  covers, then by induction
we may find three  H_i  in  T \subset S  which cover. So we may assume
T  does not cover, that is, there is  a point  P_H  in  H  which is
not in any other half-plane in  S. We will show this is not possible 
with  n >= 4.

Pick any four such points, say  P1, P2, P3, P4.  Since, for example,
P2, P3, and P4  all lie in the complement of  H_1, their convex hull does
as well, and so does not contain  P1. So the convex hull of the four
points is a quadrilateral. Label the four so that  P1, P2, P3, P4  are the 
vertices of this quadrilaterial in clockwise order. Then the line segments
P1-P3 and P2-P4 intersect at a point  P.

Now, for every half-plane  H  in  S  except  H1  and  H3, both P1 and P3 lie
in the complement of  H, and so the line segment joining them does as well,
and in particular,  P  is not in  H. Likewise, for every  H  except  H2 and
H4,  the complement of  H  includes  P2 and P4, hence P2-P4, hence  P.
We conclude  P  is not in any  H  in  S, contradicting the assumption that
S  covers.

\qed.

Note that the proof is false if the initial set  S  is infinite; for example
if  H_i = {(x,y) : y <= i}  then  S  covers even though no finite subset does.


I asked a colleague in optimization about this problem, since we can recast it
as the following problem: we are given  m  half-spaces through the origin in  
R^n  whose intersection consists only of  {0}, so that we have an  m x n matrix
A  for which the feasible set described by the inequalities  A v >= 0  
consists only of  {0}.  We wish to pick out  n  rows of  A  to get a matrix
B  with  {v ; B v >= 0} also equal to {0}. I take it Farkas's theorem
presents a dichotomy: if  A v >=0 has no solutions then  (A^t) w >= 0 must,
from  which the submatrix  B  may be selected using a dimension argument.
I have not pressed for details.

dave
==============================================================================

From: rusin@vesuvius.math.niu.edu (Dave Rusin)
Newsgroups: sci.math
Subject: Re: Help needed on proving that 3 half-planes are enough
Date: 14 Oct 1998 20:43:53 GMT

Normand Grégoire <normand@contact.net> wrote:

>We have a set P of n half-planes (n>3), covering R2.  Prove that some subset
>of three half-planes of P is enough to cover R2.

I gave a proof using convexity which would require a bit of tinkering 
to cover the obvious generalizations to  R^n. I should have realized at
that point that this was _only_ about convexity, and that therefore we
could appeal to Helly's theorem:
	If { C_i } is a finite set of convex subsets of  R^n  which have the 
	property that all sets of  n+1  of them have a point in common,
	then all the  C_i  have a point in common.
This proves the desired result by taking  C_i  to be the complement of
the half-space  H_i.

E. Helley, Ueber Mengen konvexer Koerper mit gememschaftliches Punkten,
Jber. DMV 32 (1923) 175-176.

dave