Stabbing pairwise intersecting disks by five points

Sariel Har-Peled, Haim Kaplan, Wolfgang Mulzer, Liam Roditty, Paul Seiferth, Micha Sharir, Max Willert

Research output: Contribution to journalArticlepeer-review

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 languageEnglish (US)
Article number112403
JournalDiscrete Mathematics
Volume344
Issue number7
DOIs
StatePublished - Jul 2021

Keywords

  • Disk intersection graph
  • LP-type problem
  • Stabbing set

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Fingerprint

Dive into the research topics of 'Stabbing pairwise intersecting disks by five points'. Together they form a unique fingerprint.

Cite this