Stabbing pairwise intersecting disks by five points
Sariel Har-Peled, Haim Y. Kaplan, Wolfgang Mulzer, Liam Roditty, Paul Seiferth, Micha Sharir, Max Willert · Discrete Mathematics · 2021
Suppose we are given a set D of n pairwise intersecting disks in the plane. A planar point set P stabs D if and only if each disk in D contains at least one point from P . We present a deterministic algorithm that takes O ( n ) time to find five points that stab D . Furthermore, we give a simple example of 13 pairwise intersecting disks that cannot be stabbed by three points. Moreover, we present a simple argument showing that eight disks can be stabbed by at most three points. This provides a simple – albeit slightly weaker – algorithmic version of a classical result by Danzer that such a set D can always be stabbed by four points.