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.
Original language | English (US) |
---|---|
Article number | 112403 |
Journal | Discrete Mathematics |
Volume | 344 |
Issue number | 7 |
DOIs | |
State | Published - Jul 2021 |
Keywords
- Disk intersection graph
- LP-type problem
- Stabbing set
ASJC Scopus subject areas
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics