An open half-plane is the set of all points lying to one side of a line, but excluding the points on the line itself. If four open half-planes cover the plane, show that one can select three of them which still cover the plane.
Solution
This seems to be one of those tiresome questions which requires careful enumeration!
Suppose first that two lines are parallel. wlog we may consider them to be horizontal. Note first that if there are more than two lines all parallel, then all but two are redundant, because we need only keep L the highest boundary of a plane that extends downwards and L' the lowest boundary of a plane that extends upwards (if one of these does not exist, then all but one line is redundant). If L' is lower than L, then their half-planes cover the plane and the other half-planes are redundant. So assume that L' is higher than L, leaving the strip between them uncovered.
Now suppose the other two boundary lines M and M' are also parallel.
The corresponding half-planes must cover the plane except for the strip between M and M', because otherwise they either cover the plane completely (in which case L and L' are redundant) or one of them is redundant. But now it is clear that the two non-parallel strips (between L and L' and between M and M') have a non-empty intersection which is not covered by any half-plane. Contradiction. So we can assume that M and M' are not parallel. So assume there is just one pair of parallel lines L and L'.
So if M is one of the other lines then it meets both L and L', leaving a half-strip uncovered as shown. The fourth half-plane must include this entire half-strip, so it must meet L and L' to the right of A and B. So it must meet M above L or below L'. If it meets above L, then L' is redundant, and if it meets below L' then L is redundant.
So we can now assume that no two lines are parallel. Take L and L' to be two of the lines. Their half-planes cover the whole plane except for a sector:
A half-plane with boundary M as illustrated is redundant. The complement of this half-plane (with the same boundary M, but pointing the other way) covers the entire plane with L and L', so the fourth half-plane is redundant. It is also easy to see that if M passes through X, then either one of L, L', M is redundant or the fourth half-plane is redundant.
So it remains to consider the case where if the other two half-planes have boundaries M and M', then both M and M' meet both arms of the uncovered sector.
Now the half-planes with boundary M, M' cannot both include X or the points in the sector far from X will not be covered by any half-plane. So suppose the half-plane with boundary M does not include X (as illustrated). Now the triangle formed by L,L',M must lie entirely in the half-plane bounded by M'. Take the vertex of the triangle closest to M' (this must be unique since we are assuming no parallel lines). wlog it is the intersection of L and L'. Now the M', L and L' half-planes cover the plane, because the sector not covered by the L and L' half-planes lies entirely in the M' half-plane.
© John Scholes
jscholes@kalva.demon.co.uk
29 Oct 2003
Last corrected/updated 29 Oct 03