 | Up to |  | Home |  | Maths |
 | Site Map | | |  | Text version |
|
|
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
half-planes
(n>3),
covering
R2. |
I spent some fruitless time trying to work with configurations of half-planes 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 half-planes covering the plane, when can we discard one as being redundant? When all its points are covered by other half-planes. So, if a half-plane h can't be discarded as redundant, there must be at least one point in R2 which is only covered by h.
Let H = {h1, h2, ..., hn} be a set of n>3 half-planes which cover R2. Assume no proper subset of H covers R2. We therefore have a set of points P = {p1, p2, ... pn}, each pk covered only by the half-plane hk.
Lemma: If we have a half-plane 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 pb lies on the line segment joining pa and pc (i.e. on the convex hull of the set { pa, pc } then by the lemma, since pa & pc lie outside the half-plane hb, all points on the line segment, including pb, lie outside hb, but this contradicts pb lies in hb. Similarly, no point lies in the triangle bound by the another 3 -- the interior of the triangle lies outside the interior point's half-plane, implying the interior point also lies outside its half-plane. 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 non-adjacent vertices pa and pb. The diagonal pa-pb intersects the convex hull of the remaining points P' at some point x. Now, x lies outside ha (resp. hb) since it lies on the convex hull of P', each point of which lies outside ha (resp. hb). Similarly, for each of the remaining points pk in P', x lies outside hk since x lies on the convex hull of {pa, pb}, each point of which lies outside hk. So x doesn't lie in any of the half-planes in H which collectively cover R2, therefore no such set P exists, therefore the assumption that no proper subset of H covers R2 is false - some proper subset H' of H covers R2. By repeating the argument with H', some subset of n<=3 half-planes in H is sufficient to cover R2.
The problem can be generalised to d dimensions as:
We have a set H of n half-spaces (n>d+1), covering Rn.
Prove that some subset of d+1 half-spaces of H is enough to cover Rn.
by an analogous proof to the one above by using Radon's Theorem:
Any set of d+2 points in Rd 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 Rd; adding extra points to the set can only create larger convex hulls.
Let H = {h1, ..., hn} be a set of n>d+1 half-spaces which covers Rn. Assume no proper subset of H covers Rn. We therefore have a set of points P = {p1, p2, ... pn}, each pk covered only by the half-space hk. Since n>d+1, P can be partitioned into two subsets V1 & V2 whose convex hulls intersect at some point x which. For each pi in V1, x isn't covered by corresponding hi since x lies within the convex hull of V2, each point of which lies outside the half-space hi; similarly for each pj in V2. So x doesn't lie in any of the half-spaces of H which by definition covers Rn, hence no such set P exists, hence the assumption that no proper subset of H covers Rn is false - some proper subset H' of H covers Rn. By repeating the argument with H', some subset of n<=d+1 half-spaces in H is sufficient to cover Rn.
|
|
| ||||||||||
