From:wpt@princeton.UUCP (William Thurston)Newsgroups:sci.mathSubject:beam detectorsDate:10 Nov 86 23:05:03 GMTOrganization:Dept. of Computer Science, Princeton UniversityKeywords:points, lines, Sylvester's problem

... 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

From:eppstein@garfield.columbia.eduTo:princeton!wptSubject:Beam detectors etc

I haven't solved your problem, which was to find a better lower bound than pi for a beam detector for the unit circle. However I have found a better detector than the one you gave (square bow and arrow, total length pi/2 + 2 + sqrt(2) = ~4.985). It looks a lot like the bow and arrow, but it's based on a hexagon. It can be found by extending the ends of a semicircle to the vertices of a circumscribing hexagon, and adding a line segment from the remaining vertex halfway to the center. I guess that's not a very clear description, but anyway it's a beam detector and its length is pi + sqrt(3) = ~4.874. So is this new or interesting? Also this led me to a couple of conjectures, which I wonder if you could comment on. First, is the best detector for a triangle known to be a Steiner tree on its vertices? Second, is it known that a minimum detector for any set consists of only straight line segments except possibly for parts of the set's convex hull? I don't have any idea how to prove either of these but they seem reasonable... ...

Date:Sunday, 16 November 1986 15:38-ESTFrom:seismo!princeton!wpt at columbia.eduTo:eppstein at garfield.columbia.edu

I don't know what the best currently known beam detector for the circle is; someone at Bell Labs must know, I'll inquire. There are supposed to be various improvements on the square bow and arrow, but I haven't actually seen descriptions. I would be very surprised if anyone had proved that the best beam detector for a triangle was a Steiner tree --- to prove such a thing would probably also give a proof that you need more than pi for a circle. ... Bill Thurston

Date:Tuesday, 18 November 1986 20:47-ESTFrom:seismo!research!shannon!amo at columbia.eduTo:princeton!fisher!doyle at columbia.edu, wpt at princeton.UUCP, eppstein at garfield.columbia.edu

I haven't worked on this problem myself, but I have talked to my colleagues at Bell Labs in Murray Hill who have. It appears that the best beam detector that's known is due to E. Makai. He published in 1980 an abstract, of which we have a copy, and which is reviewed in Zentralblatt 459/52005. In it he says that a bow-and-arrow construction (section of the boundary of a circle, segments of the tangents to the circle at the endpoints, and a segment perpendicular to the line connecting the ends of the circle segments) gives a set of length 4.8189.... In a recent letter to Larry Shepp, he pointed out that this construction can be improved by about 1/10000. If the endpoints of the circle segments are R and S, and the two tangent line segments are RQ and PS, then one can replace RQ by the altitude from Q of the triangle PQR. A few further modifications of this kind ought to give slight further improvements, accoring to Makai. Andrew Odlyzko