Stabbing Pairwise Intersecting Disks by Five Points

University of Ottawa

I will present a paper that appeared on arXiv on January 11, 2018, by Sariel Har-Peled, Haim Kaplan, Paul Seiferth, Wolfgang Mulzer, Micha Sharir, Liam Roditty and Max Willert.

They present an $O(n)$ expected time algorithm and an $O(n\log(n))$ deterministic time algorithm to find a set of five points that stab a set of $n$ pairwise intersecting disks in the plane. They also give a simple construction with $13$ pairwise intersecting disks that cannot be stabbed by three points.