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"]Barrer 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 barrier 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. 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. 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. 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"]BARRIER 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.