184 11. Combinatorics in Geometry
edge of the blackboard tilts a little to the left (else, we tilt the blackboard
by a tiny amount).
Now consider the lowest point in each region on the blackboard. Each
region has exactly one lowest point, since all regions are finite, and the
bordering lines are not horizontal. This lowest point is then an intersection
point of two of our lines, or the intersection point of a line with the lower
edge of the blackboard, or the lower left corner of the blackboard. Further-
more, each of these points is the lowest point of one and only one region.
For example, if we consider any intersection point of two lines, then we see
that four regions meet at this point, and the point is the lowest point of
exactly one of them.
Thus the number of lowest points is the same as the number of intersec-
tion points of the lines, plus the number of intersection points between lines
and the lower edge of the blackboard, plus one for the lower left corner of
the blackboard. Since any two lines intersect, and these intersection points
are all different (this is where we use that the lines are in general position),
the number of such lowest points is
(n
2)
+n+1. 11.3 Convex Polygons
Let us finish our excursion to combinatorial geometry with a problem that
can be easily stated, but which is still unsolved. It is often called theHappy
End Problem, because the mathematician who raised it, Esther Klein, and
the mathematician who proved the first bounds on it, Gy ̈orgy Szekeres
(together with P ́al Erd ̋os), got married shortly after.
We start with an exercise:
Prove that if we are given five points in the plane such that no
three of them are on a line, then we can always find four points
among them that form the vertices of a convex quadrilateral.For a quadrilateral, convexity means that the two diagonals intersect
inside the quadrilateral. In Figure 11.7, the first quadrilateral is convex;
the second is concave.
FIGURE 11.7. A convex and a concave quadrilateral.