Barrier problem née archer problem

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.

Barrer

Examples (1) and (2) are barriers, while (3) is not.

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.

Figure 1.  The barrier

Figure 1. The given barrier has length 3.

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!

Figure 2.

Figure 2. The given barrier has length 1 + √3.

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

Figure 3.

Figure 3. This disconnected barrier has length 2 + √2/2.

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.

Figure 4.

Figure 4. This barrier has length √2 + √6/2.

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

BARRIER

Figure 5. This barrier has length approxmately 4.79989.

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.