@article{582c861cea6b477ea6bc87117395b503,
title = "Stabbing pairwise intersecting disks by five points",
abstract = "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.",
keywords = "Disk intersection graph, LP-type problem, Stabbing set",
author = "Sariel Har-Peled and Haim Kaplan and Wolfgang Mulzer and Liam Roditty and Paul Seiferth and Micha Sharir and Max Willert",
note = "Funding Information: A preliminary version appeared as S.Har-Peled, H.Kaplan, W.Mulzer, L.Roditty, P.Seiferth, M.Sharir, and M.Willert. Stabbing Pairwise Intersecting Disks by Five Points. Proc.29th ISAAC, pp.50:1–50:12. SHP was supported by NSF, USA AF awards CCF-1421231, and CCF-1217462. WM was supported by DFG, Germany grant MU/3501/1 and ERCSTG 757609. PS was supported by DFG, Germany grant MU/3501/1. MS was supported by ISF, Israel grant 892/13 and 260/18, by the Israeli Centers of Research Excellence (I-CORE) program (Center No. 4/11), and by the Blavatnik Research Fund in Computer Science at Tel Aviv University, Israel. HK was supported by ISF, Israel grants 1595-19 and the Blavatnik Family Foundation, USA. Work on this paper was supported in part by grants 1367/2016 and 1161/2011 from the German–Israeli Science Foundation (GIF), Israel. Funding Information: A preliminary version appeared as S.Har-Peled, H.Kaplan, W.Mulzer, L.Roditty, P.Seiferth, M.Sharir, and M.Willert. Stabbing Pairwise Intersecting Disks by Five Points. Proc.29th ISAAC, pp.50:1–50:12. SHP was supported by NSF, USA AF awards CCF-1421231 , and CCF-1217462 . WM was supported by DFG, Germany grant MU/3501/1 and ERC STG 757609 . PS was supported by DFG, Germany grant MU/3501/1 . MS was supported by ISF, Israel grant 892/13 and 260/18 , by the Israeli Centers of Research Excellence (I-CORE) program (Center No. 4/11), and by the Blavatnik Research Fund in Computer Science at Tel Aviv University, Israel . HK was supported by ISF, Israel grants 1595-19 and the Blavatnik Family Foundation, USA . Work on this paper was supported in part by grants 1367/2016 and 1161/2011 from the German–Israeli Science Foundation (GIF), Israel . Publisher Copyright: {\textcopyright} 2021 Elsevier B.V.",
year = "2021",
month = jul,
doi = "10.1016/j.disc.2021.112403",
language = "English (US)",
volume = "344",
journal = "Discrete Mathematics",
issn = "0012-365X",
publisher = "Elsevier",
number = "7",
}