@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 = "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",
}