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.

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 bodyCin the plane, what is the smallest total length of a barrierT? Typically there are additional constraints:Cis a polygon;Tis a union of line segments; the barrierTlies in the interior ofC, or in the exterior.

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!

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).

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.

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).

## Generalizations

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:

- An optimal barrier for a square is interior to the square.
- An optimal exterior barrier for the unit square has length 3.

## References

[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.