From:           wpt@princeton.UUCP (William Thurston)
Newsgroups:     sci.math
Subject:        beam detectors
Date:           10 Nov 86 23:05:03 GMT
Organization:   Dept. of Computer Science, Princeton University
Keywords:       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.edu
To:             princeton!wpt
Subject:        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-EST
From:           seismo!princeton!wpt at columbia.edu
To:             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-EST
From:           seismo!research!shannon!amo at columbia.edu
To:             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