Stabbing pairwise intersecting disks by five points

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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.

Original languageEnglish (US)
Title of host publication29th International Symposium on Algorithms and Computation, ISAAC 2018
EditorsChung-Shou Liao, Wen-Lian Hsu, Der-Tsai Lee
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Pages50:1-50:12
ISBN (Electronic)9783959770941
DOIs
StatePublished - Dec 1 2018
Event29th International Symposium on Algorithms and Computation, ISAAC 2018 - Jiaoxi, Yilan, Taiwan, Province of China
Duration: Dec 16 2018Dec 19 2018

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume123
ISSN (Print)1868-8969

Conference

Conference29th International Symposium on Algorithms and Computation, ISAAC 2018
CountryTaiwan, Province of China
CityJiaoxi, Yilan
Period12/16/1812/19/18

Keywords

  • Disk graph
  • LP-type problem
  • Piercing set

ASJC Scopus subject areas

  • Software

Cite this