2026-08-16T08:14:48Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9998 2024-03-06T10:45:18Z ddc:004 open_access

Stabbing Pairwise Intersecting Disks by Five Points Har-Peled, Sariel Kaplan, Haim Mulzer, Wolfgang Roditty, Liam Seiferth, Paul Sharir, Micha Willert, Max Disk graph piercing set LP-type problem 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sariel Har-Peled and Haim Kaplan and Wolfgang Mulzer and Liam Roditty and Paul Seiferth and Micha Sharir and Max Willert 2018 Is Part Of LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2018.50 urn:nbn:de:0030-drops-99989 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.50 eng https://creativecommons.org/licenses/by/3.0/legalcode