Stabbing Pairwise Intersecting Disks with Five Points

Authoritative PDF · Markdown reading copy

Sariel Har-Peled

Abstract

We present a significantly simpler proof of the following. Every set of disks in the plane that is pairwise intersecting can be stabbed by five points. This specific version has a relatively short proof by Har-Peled et al. [HKM+21], but our proof is both shorter and simpler. It was, of course, generated largely by using AI tools. Specifically, ChatGPT (Astra) and Anthropic (Fable).

1 Proof

The input is a set of (say) \(n\) (closed) disks such that every pair of them intersects. The question is how many points are required to stab them. It is known that four are enough, but proving this requires quite a bit of work. Fortunately, showing that five points are sufficient is significantly easier [HKM+21].

Scope and notation. Write \(B(c,r)=\{z:\Vert z-c\Vert \le r\}\) for the closed ball of radius \(r\) centered at \(c\). A set of points stabs a family if it meets every member.

1.1 Four expanding disks cover the center lens

Figure 1.1: Illustrating the proof of Lemma 1.1.

Lemma 1.1. Let \(D_1, D_2\) be two disks of radius \(r\), \(r>0\), with centers at distance at least \(\sqrt {3}r\). Then there are four points that stab all the disks of radius at least \(r\) intersecting both \(D_1\) and \(D_2\).

Proof: Scale, rotate and translate the plane so that \(r=1\), and the two centers are at \(u=(-a,0)\) and \(v=(a,0)\), where \(a\ge \sqrt 3/2\). Let \(P=\{p_1,p_2,p_3,p_4\}\), where

\[p_1=(1,0),\quad p_2=(0,1),\quad p_3=(-1,0),\quad p_4=(0,-1).\]

First consider a unit disk with center \(z=(x,y)\) meeting both reference disks. By symmetry, assume \(x,y\ge 0\). We have that

\[x+y =\left\Vert {z -u} \right\Vert _1 - a \le \sqrt 2\Vert z-u\Vert -a\le 2\sqrt 2-a<2.\]

Thus, by symmetry, every such center lies in the diamond (see Figure 1.1)

\[Q=\left\{ \bigl .(x,y) \;\middle\vert\; \vert x\vert +\vert y\vert \leq 2 \right\}.\]

The lines \(y=\pm x\) divide \(Q\) into four squares of circumradius one, centered at the points of \(P\). Hence the unit disks centered at \(P\) cover \(Q\), so every unit disk meeting both reference disks contains a point of \(P\).

Now consider a disk of radius \(t>1\) meeting both reference disks, with center in the right half-plane; see Figure 1.1. Move its center toward \(u\), reducing its radius by the distance traveled, until its radius is one or its center reaches the \(y\)-axis. The shrinking disk stays inside the original disk. It continues to meet \(B(u,1)\), since its radius and its distance to \(u\) decrease equally. It also meets \(B(v,1)\), since \(v\) is no farther from its center than \(u\) while the center remains in the right half-plane.

If the final radius is one, the preceding argument applies. Otherwise, write the final disk as \(B((0,y),s)\), where \(s\ge 1\). Since it meets \(B(u,1)\), we have \(\vert y\vert \le s+1\), and consequently

\[\min \{\Vert (0,y)-p_2\Vert ,\Vert (0,y)-p_4\Vert \} =\bigl \vert \vert y\vert -1\bigr \vert \le s.\]

In either case the final disk, and hence the original disk, contains a point of \(P\). The left half-plane follows by symmetry.

1.2 The fifth point also selects the pair

Theorem 1.2. Every finite pairwise intersecting family of closed planar disks can be stabbed by at most five points.

Proof: The empty family needs no points; for a family with common intersection one point suffices. A radius-zero disk would give such a common point. Otherwise order the disks \(D_i=B(c_i,r_i)\) by nondecreasing radius, breaking ties arbitrarily. Let \(k\) be the first index with empty prefix intersection. The set \(K=D_1\cap \cdots \cap D_{k-1}\) is nonempty and compact. Choose its point \(p\) closest to \(c_k\); since \(K\cap D_k\) is empty, \(\Vert p-c_k\Vert >r\), where \(r=r_k\). We next show that four points stab the suffix \(D_k,\ldots ,D_n\). This proves the theorem, since \(p\) stabs the prefix \(D_1,\ldots ,D_{k-1}\).

Enlarge every prefix disk to radius \(r\), moving its center away from \(p\) by the increase in radius (in any direction if its center is \(p\)). Each enlarged disk contains the original. This preserves the supporting tangents at \(p\), so \(p\) remains the point of their intersection closest to \(c_k\). Keep the notation \(D_i,c_i,K\) for the enlarged prefix disks, their centers, and their intersection.

Figure 1.2: The two enlarged prefix disks (red) and \(D_k\) (blue) have radius \(r\). Their centers form a triangle containing \(p\), with \(\Vert p-c_i\Vert =\Vert p-c_j\Vert =r\) and \(\Vert p-c_k\Vert >r\). Two of the three rays from \(p\) form an angle of at least \(120^\circ\).

Suppose first that \(p\) is a vertex of the boundary of \(K\). Since \(p\) is closest to \(c_k\), we can choose two prefix disks whose boundaries pass through \(p\), with centers \(c_i,c_j\), such that \(p\) lies in the triangle with vertices \(c_i,c_j,c_k\); see Figure 1.2. We allow a singleton \(K\) and a degenerate triangle. Two of the three rays from \(p\) to the centers therefore form an angle of at least \(120^\circ\). Both centers are at distance at least \(r\) from \(p\), so their distance is at least \(\sqrt 3\,r\). If \(p\) is instead on a smooth boundary arc, its center \(c_i\) lies on the ray from \(c_k\) through \(p\), giving \(\Vert c_i-c_k\Vert =r+\Vert p-c_k\Vert >2r\).

The selected disks have radius \(r\). Every suffix disk has radius at least \(r\) and meets both selected disks, because it meets their originals. By Lemma 1.1, four points stab the suffix. Explicitly, if \(m\) is the midpoint of the selected centers and \(e\) is a unit vector along their line, the five points are \(p\), \(m\pm re\), and \(m\pm re^\perp\).

References

[HKM+21] S. Har-Peled, H. Kaplan, W. Mulzer, L. Roditty, P. Seiferth, M. Sharir, and M. Willert. Stabbing pairwise intersecting disks by five points. Discret. Math., 344(7): 112403, 2021.