In discrete geometry, an opaque set is a system of curves or other set in the plane that blocks all lines of sight across a polygon, circle, or other shape. Opaque sets have also been called barriers, beam detectors, opaque covers, or (in cases where they have the form of a forest of line segments or other curves) opaque forests. Opaque sets were introduced by Stefan Mazurkiewicz in 1916, and the problem of minimizing their total length was posed by Frederick Bagemihl in 1959. For instance, visibility through a unit square can be blocked by its four boundary edges, with length 4, but a shorter opaque forest blocks visibility across the square with length 2 + 1 2 6 ≈ 2.639 {\displaystyle {\sqrt {2}}+{\tfrac {1}{2}}{\sqrt {6}}\approx 2.639} . It is unproven whether this is the shortest possible opaque set for the square, and for most other shapes this problem similarly remains unsolved. The shortest opaque set for any bounded convex set in the plane has length at most the perimeter of the set, and at least half the perimeter. For the square, a slightly stronger lower bound than half the perimeter is known. Another convex set whose opaque sets are commonly studied is the unit circle, for which the shortest connected opaque set has length 2 + π {\displaystyle 2+\pi } . Without the assumption of connectivity, the shortest opaque set for the circle has length at least π {\displaystyle \pi } and at most 4.7998 {\displaystyle 4.7998} . Several published algorithms claiming to find the shortest opaque set for a convex polygon were later shown to be incorrect. Nevertheless, it is possible to find an opaque set with a guaranteed approximation ratio in linear time, or to compute the subset of the plane whose visibility is blocked by a given system of line segments in polynomial time.
Definitions Every set S {\displaystyle S} in the plane blocks the visibility through a superset of S {\displaystyle S} , its coverage C {\displaystyle C} . C {\displaystyle C} consists of points for which all lines through the point intersect S {\displaystyle S} . If a given set K {\displaystyle K} forms a subset of the coverage of S {\displaystyle S} , then S {\displaystyle S} is said to be an opaque set, barrier, beam detector, or opaque cover for K {\displaystyle K} . If, additionally, S {\displaystyle S} has a special form, consisting of finitely many line segments whose union forms a forest, it is called an opaque forest. There are many possible opaque sets for any given set K {\displaystyle K} , including K {\displaystyle K} itself, and many possible opaque forests. 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, the one-dimensional Hausdorff measure can be used, which agrees with the standard length in the cases of line segments and rectifiable curves. Most research on this problem assumes that the given set K {\displaystyle K} is a convex set. When it is not convex but merely a connected set, it can be replaced by its convex hull without changing its opaque sets. Some variants of the problem restrict the opaque set to lie entirely inside or entirely outside K {\displaystyle K} . In this case, it is called an interior barrier or an exterior barrier, respectively. When this is not specified, the barrier is assumed to have no constraints on its location. Versions of the problem in which the opaque set must be connected or form a single curve have also been considered. It is not known whether every convex set P {\displaystyle P} has a shortest opaque set, or whether instead the lengths of its opaque sets might approach an infimum without ever reaching it. Every opaque set for P {\displaystyle P} can be approximated arbitrarily closely in length by an opaque forest, and it has been conjectured that every convex polygon has an opaque forest as its shortest opaque set, but this has not been proven.
Bounds When the region to be covered is a convex set, the length of its shortest opaque set must be at least half its perimeter and at most its perimeter. For some regions, additional improvements to these bounds can be made.
… excerpt ends here. Continue reading the full article.
