Home Bookmarks Papers Blog

# Stabbing pairwise intersecting disks by five points

Sariel Har-Peled, Haim Kaplan, Wolfgang Mulzer, Liam Roditty, Paul Seiferth, Micha Sharir, and Max Willert.
We present an $O(n)$ expected time algorithm and an $O(n \log n)$ deterministic algorithm to find a set of five points that stab a set of $n$ pairwise intersecting disks in the plane. We also give a simple construction with 13 pairwise intersecting disks that cannot be stabbed by three points.
PDF. : arXiv : DBLP.