I first came across this problem in 1986, when Bill Thurston posted a message about it to sci.math, and soon exchanged correspondence on the subject with him and others including Andrew Odlyzko. Thurston's original message described a beam detector in the shape of a "bow and arrow": one circumscribes the circle by a square, extends a quarter-circle by line segments to two opposite square corners (the "bow"), and drops a half-diagonal from the remaining corner to the center of the figure (the "arrow"). This detector is drawn below, and has total length pi/2 + 2 + sqrt(2), approximately 4.985.

Thurston also included a proof (based on the theory of measures on spaces of lines) that the length of any beam detector must be at least pi. The point of his message was to ask for better lower bounds.

My response to this message was to modify this bow and arrow, basing it on a hexagon instead of a square. It soon became clear that others had looked at modified bow-and-arrow beam detectors, including E. Makai, who had published in 1980 a construction with length 4.8189. He later noted that one of the segments forming an end of the "bow" can be separated and tilted to form another "arrow", making a very small further improvement.

Since then, several articles have appeared on the subject of "opaque
forests". This is apparently the same idea as that of a beam detector,
with three changes. First, the detector is explicitly required to be a
forest (set of line segments). Second, the set of lines that must be
detected is that crossing some particular polygon, rather than a circle.
And third, the detector must be contained entirely within that polygon.
This third restriction changes the problem completely;
for the circle, all boundary points would have to be part of such
a forest, and the total length would be 2 pi.
Some early works on this subject assumed that generalizations of the bow-and-arrow idea gave the correct solution, but T. Shermer in 1991 showed
that in some cases one can find a better opaque forest by keeping everything connected (computing a *Steiner tree*).

My latest (but half-baked) idea for a beam detector combines the hexagon, bow and arrow, and Steiner tree. Start with a hexagon ABCDEF circumscribing the circle. Connect vertices ABDE with a Steiner tree. Finally, drop a line segment from the remaining two vertices C and F to the nearest side of quadrilateral ABDE. But for the regular hexagon (illustrated below), this produces a beam detector with total length 2/sqrt 3 + 4, approximately 5.1547, not bad but worse than the bow and arrow. (Thanks to John Rickard for the length; I initially miscalculated this value to be 4.464.) I suspect (but have not calculated) that non-regular hexagons can be used to improve this value even further, but maybe that would still not be enough to get a better beam detector.

The latest news in Scientific American is of a constructor by J. Day with length 4.7998, but this is not much of an improvement on Makai's bound, and looks like it may be the same as Makai's old two-arrow improvement. Is there a better beam detector?

References:

- V. Akman. "An algorithm for determining an opaque minimal forest of
a convex polygon".
*Inf. Proc. Lett.*24 (1987) 193-198. - K. Brakke. "Opaque Square and Opaque Cube".
- P. Dublish. "An O(n^3) algorithm for finding the minimal opaque
forest of a convex polygon".
*Inf. Proc. Lett.*29 (1988) 275-276. - S. Finch. "Beam Detection Constant". MathSoft, Inc.
- E. Makai. "On a dual of Tarski's plank problem".
Diskrete Geometrie, 2. Kolloq., Inst. Math. Univ. Salzburg (1980) 127-132;
reviewed in
*Zentralblatt*459/52005. - T. Shermer. "A counterexample to the algorithms for determining opaque minimal forests".
*Inf. Proc. Lett.*40 (1991) 41-42. - J. Steprans.
"Digging the shortest trench to uncover a pipeline".
- I. Stewart. "The great drain robbery".
*Scientific American*, Sept. 1995; feedback, Feb. 1996.

From the Geometry Junkyard,
computational
and recreational geometry.

David Eppstein,
Theory Group,
ICS,
UC Irvine.

Last update: .