Examples (1) and (2) are barriers, while (3) is not.[/caption]Submitted by Matthew Stone (Ross counselor and Yale undergraduate)
A collection of line segments contained in a unit square is said to be a barrier if every straight line that crosses the square cuts one of those line segments. Note: A barrier is not required to be connected.
[caption id="attachment_498" align="aligncenter" width="600"] Examples (1) and (2) are barriers, while (3) is not.[/caption]
The length of barrier (1) is 2√2 ≈ 2.828 units. The length of barrier (2) is shorter (with length depending on the location of those interior intersection points). Can you find a barrier of shorter length? What is the smallest possible length for such a barrier?
The barrier problem has many variations and generalizations, but the original problem is easily stated. Suppose a convex set C in the plane is given. A set T is called an opaque set or a barrier for C if every line that passes through C also meets T.
Problem. For a convex body C in the plane, what is the smallest total length of a barrier T? Typically there are additional constraints: C is a polygon; T is a union of line segments; the barrier T lies in the interior of C, or in the exterior.
[caption id="attachment_500" align="alignright" width="188"]
Figure 1. The given barrier has length 3.[/caption]
This barrier problem was first introduced by Mazurkiewicz in 1916, but a solution has not been found even when C is a unit square. Some initial steps are mentioned below…but please stop reading right now, and try to find a few solutions for yourself before continuing!
[caption id="attachment_501" align="alignleft" width="188"]
Figure 2. The given barrier has length 1 + √3.[/caption]
Let MBL(C) be the minimal barrier length for convex polygon C. Let’s write p(C) for the perimeter of C. A line that meets the interior of C must cross the boundary, and consequently: MBL(C) ≤ p(C). In fact, any such line passes through two sides of C so the set T of all but one side of C is opaque. Therefore MBL(C) < p(C).
Let’s restrict attention to the case C is the unit square S. Remarks above show that MBL(S) ≤ 3 (see Figure 1).
[caption id="attachment_503" align="alignright" width="188"]
Figure 3. This disconnected barrier has length 2 + √2/2.[/caption]
If a set T inside S connects the four vertices, then T is a barrier. The optimal such formation is a Euclidean Steiner Tree on 4 vertices, as pictured in Fig. 2. Those interior angles each measure 120° and the length is 1 + √3 ≈ 2.732.
[caption id="attachment_504" align="alignleft" width="188"]
Figure 4. This barrier has length √2 + √6/2.[/caption]
But a barrier need not be connected! With some thought (and luck), a flash of insight yields a barrier built from two sides and a half-diagonal (see Figure 3). This one has length 2 + √2/2 ~ 2.707, shorter than the previous barrier. With Steiner-type moves we can optimize this two-piece version to get the barrier in Figure 4, with length √2 + √6/2 ≈ 2.639. This one is conjectured to be the shortest barrier for the square, but no one has ever found a proof (or a shorter barrier).
[caption id="attachment_515" align="alignright" width="217"]
Figure 5. This barrier has length approxmately 4.79989.[/caption]
There are many ways to generalize the barrier problem, and many of them involve non-polygonal convex bodies. For instance consider the problem for the unit disk D. In this case a barrier, or opaque set, is often known as a Beam Detector. The shortest known barriers seem to be external to D. Figure 5 shows a two-piece barrier for the unit disk; this barrier is NOT optimal. A shorter one is known. Can you find a shorter barrier for the unit disk?
While exact solutions are not known for any of those barrier problems, some upper and lower bounds have been proved. For example, if B is a barrier for convex body C, then length(B ) ≥ 12p(C). A proof is given in Reference [1].
Most questions surrounding the Barrier Problem seem to be open. In Reference [2], the authors mention some interesting problems, many of which seem obviously true… but no proofs are known. For example, two such PODASIPs are:
[1] A. Dumitrescu, M. Jiang, and J. Pach, Opaque Sets, Algorithmica 69 (2014) 315-334.
[2] A. Dumitrescu and M. Jiang , Computational Geometry Column 58, Newsletter, ACM-SIGACT News 44 (2013) 73-78.