wpt@princeton.UUCP (William Thurston) (11/11/86)
1. Several people have pointed out to me that there are other, more elementary solutions to Sylvester's problem (to show that for a non-collinear set of points in the plane, there is one pair of points such that the line through them does not go through any other points). Whether they are simpler is a question which could be debated. The other solutions involve the metric of the plane, not just the topology: proof a was to dualize, then calculate the Euler characteristic. proof b: Among all triples of non-collinear points, let (p, q, r) be a triple which minimizes the distance from p to the line through q and r. Claim: the line through q and r contains no other point s. For if q, r, and a point s are all on a single line, then two of the three --- say, q and s in that order --- are on one side of the foot of the perpendicular from p. Then (q, p, s) has a smaller distance. proof c: Transform projectively so that one point x is at infinity, and all lines through it are horizontal lines. Among all non-horizontal lines determined by two points in the set, let l be one of minimal slope. Then if l contains three points p, q and r in that order, the line xq cannot meet any other points. 2. There have been many generalizations of this. Kelly and Moser, Canadian J. Math 16(1958) showed that for a set of n points, there are at least 3n/7 determined by a pair of the points not meeting any other point. Beck (Combinatorica 3(3-4), 1983, pp.281--297 showed that there is a constant c such that if no line contains more than n-k points, the total number of lines is at least ckn. 3. Here is the unsolved problem: Given a subset S of the plane, a beam detector for S is a curve or union of curves D such that every straight line which intersects S also intersects D. Claim: If S is a convex closed curve in the plane, then the minimum length for a beam detector for S is at least half the length of S. Proof: there is a canonical measure on the set of lines in the plane: in local coordinates given by (t, theta) where t is the intersection with a line L, and (0 < theta < pi) is the angle, the measure is d t d theta. This measure does not depend on L. The total measure of lines intersecting a curve D is at most pi(length D). The total measure of lines intersecting S is pi/2 length(S), since a.e. line which hits S hits twice. QUESTION: Is there a lower bound strictly greater than pi for the length of a beam detector for the unit circle? (There are examples of beam detectors for the unit circle which have length less than 2 pi. For instance, there is a ``bow-and-arrow'' configuration inscribing the circle in a square: use a quarter of the circle, extended by two half-sides of the square, together with half of a main diagonal of the square.) Any beam detector D for the circle with length near pi would have to be mainly inside the square, and it would have to have the property that most lines which intersect D intersect it just once. Could D consist of a lot of tiny short arcs, so that when you stand on any of the arcs and look at all the others, they all tend to line up as in an orchard, but when you view D from outside the circle, you only see trees? Bill Thurston princeton!wpt