@inproceedings{b15019300d034a7fad489048e39dc0e1,

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. 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 graph, LP-type problem, Piercing 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: Partially supported by a NSF AF awards CCF-1421231, and CCF-1217462. 2 Partially supported by DFG grant MU/3501/1 and ERC STG 757609. 3 Partially supported by DFG grant MU/3501/1. 4 Partially supported by ISF Grant 892/13, by the Israeli Centers of Research Excellence (I-CORE) program (Center No. 4/11), by the Blavatnik Research Fund in Computer Science at Tel Aviv University, and by the Hermann Minkowski-MINERVA Center for Geometry at Tel Aviv University. Funding Information: Funding Work on this paper was supported in part by grant 1367/2016 from the German-Israeli Science Foundation (GIF). Funding Information: 1 Partially supported by a NSF AF awards CCF-1421231, and CCF-1217462. 2 Partially supported by DFG grant MU/3501/1 and ERC STG 757609. 3 Partially supported by DFG grant MU/3501/1. 4 Partially supported by ISF Grant 892/13, by the Israeli Centers of Research Excellence (I-CORE) program (Center No. 4/11), by the Blavatnik Research Fund in Computer Science at Tel Aviv University, and by the Hermann Minkowski-MINERVA Center for Geometry at Tel Aviv University. Work on this paper was supported in part by grant 1367/2016 from the German-Israeli Science Foundation (GIF). Publisher Copyright: {\textcopyright} Sariel Har-Peled, Haim Kaplan, Wolfgang Mulzer, Liam Roditty, Paul Seiferth, Micha Sharir, and Max Willert;; 29th International Symposium on Algorithms and Computation, ISAAC 2018 ; Conference date: 16-12-2018 Through 19-12-2018",

year = "2018",

month = dec,

day = "1",

doi = "10.4230/LIPIcs.ISAAC.2018.50",

language = "English (US)",

series = "Leibniz International Proceedings in Informatics, LIPIcs",

publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",

pages = "50:1--50:12",

editor = "Chung-Shou Liao and Wen-Lian Hsu and Der-Tsai Lee",

booktitle = "29th International Symposium on Algorithms and Computation, ISAAC 2018",

}