In the following uppercase letters will denote points in the plane
and lowercase letters will denote lines (pairs of uppercase letters,
such as PQ, will denote the line determined by points P and Q).
PTS - the given set of n points
LNS = { PQ | P,Q in PTS }
Let the pair (P,m) denote the perpendicular distance from the
point P to the line m.
PDS = { (P,m) | P in PTS, m in LNS,
and P not on m }
If PDS is the empty set, then all the points in PTS lie on one
line; otherwase, PDS is a finite (at most n2(n+1)/2 members)
non-empty set. Therefore, there exists a (P0,m0) in
PDS such that
(P0,m0) ≤ (P,m) for all (P,m) in PDS. (1)
Clearly m0 contains two or more points of PTS.
We will show that it cannot contain more than two points.
Let Q0
be the foot of the perpendicular from P0 to m0.
Assume that m0 contains three or more points of PTS. Then there
exists two of those points (P1 and P2) such that P1 = Q0
or P1 lies between Q0 and P2.
Let m1 = P0P2 and Let Q1
be the foot of the perpendicular from P1 to m1.
Let µ = /P1P2Q1 = /P0P2Q0.
Then,
|P1Q1| = |P1P2|sin(µ) = (|P1P2|cos(µ))tan(µ)
< |P1P2|tan(µ) ≤ |P2Q0|tan(µ) = |P0Q0|
or
(P1,m1) < (P0,m0) (2)
(2) contradicts (1). Therefore, the assumption that m0 contains more
than two points is false.
QED
Note: Google "Sylvester-Gallai theorem" for more info.
|
