Opaque set
Opaque sets were introduced by Stefan Mazurkiewicz in 1916,[1] and the problem of minimizing their total length was posed by Frederick Bagemihl in 1959.
It is unproven whether this is the shortest possible opaque set for the square, and for most other shapes this problem similarly remains unsolved.
Several published algorithms claiming to find the shortest opaque set for a convex polygon were later shown to be incorrect.
For opaque forests, or more generally for systems of rectifiable curves, their length can be measured in the standard way.
For more general point sets, one-dimensional Hausdorff measure can be used, and agrees with the standard length in the cases of line segments and rectifiable curves.
Versions of the problem in which the opaque set must be connected or form a single curve have also been considered.
that are strictly convex, meaning that there are no line segments on the boundary, and for interior barriers, this bound is tight.
[5] The same reasoning shows that for interior barriers of convex polygons, all vertices must be included.
[4] However, for interior barriers of non-polygonal convex sets that are not strictly convex, or for barriers that are not required to be connected, other opaque sets may be shorter; for instance, it is always possible to omit the longest line segment of the boundary.
by a strictly convex superset, which can be chosen to have perimeter arbitrarily close to the original set.
By the Crofton formula, the lengths of the boundary and barrier have the same proportion as these expected numbers.
[7] For a triangle, as for any convex polygon, the shortest connected opaque set is its minimum Steiner tree.
Izumi has proven a small improvement to the perimeter-halving lower bound for the equilateral triangle.
It consists of the minimum Steiner tree of three of the square's vertices, together with a line segment connecting the fourth vertex to the center.
Ross Honsberger credits its discovery to Maurice Poirier, a Canadian schoolteacher,[11] but it was already described in 1962 and 1964 by Jones.
[7] The perimeter-halving lower bound of 2 for the square, already proven by Jones,[12][13] can be improved slightly, to
[6] The case of the unit circle was described in a 1995 Scientific American column by Ian Stewart, with a solution of length
Vance Faber and Jan Mycielski credit this single-curve solution to Menachem Magidor in 1974.
[19] The unknown length of the optimal solution has been called the beam detection constant.
[20] Two published algorithms claim to generate the optimal opaque forest for arbitrary polygons, based on the idea that the optimal solution has a special structure: a Steiner tree for one triangle in a triangulation of the polygon, and a segment in each remaining triangle from one vertex to the opposite side, of length equal to the height of the triangle.
In particular, for a long thin rectangle, the minimum Steiner tree of all four vertices is shorter than the triangulation-based solution that these algorithms find.
[23] No known algorithm has been guaranteed to find a correct solution to the problem, regardless of its running time.
[4] There has also been more successful study of approximation algorithms for the problem, and for determining the coverage of a given barrier.
[25] Although optimal in the worst case for inputs whose coverage region has combinatorial complexity matching this bound, this algorithm can be improved heuristically in practice by a preprocessing phase that merges overlapping pairs of hulls until all remaining hulls are disjoint, in time
[26] Mazurkiewicz (1916) showed that it is possible for an opaque set to avoid containing any nontrivial curves and still have finite total length.
[1] A simplified construction of Bagemihl (1959), shown in the figure, produces an example for the unit square.
[1] Other early works on opaque sets include the papers of H. M. Sen Gupta and N. C. Basu Mazumdar in 1955,[27] and by Frederick Bagemihl in 1959,[2] but these are primarily about the distance sets and topological properties of barriers rather than about minimizing their length.
They have been repeatedly posed, with multiple colorful formulations: digging a trench of as short a length as possible to find a straight buried telephone cable,[8] trying to find a nearby straight road while lost in a forest,[17] swimming to a straight shoreline while lost at sea,[4] efficiently painting walls to render a glass house opaque,[28] etc.
In three dimensions, the corresponding question asks for a collection of surfaces of minimum total area that blocks all visibility across a solid.
However, for some solids, such as a ball, it is not clear whether such a collection exists, or whether instead the area has an infimum that cannot be attained.
