License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2018.50
URN: urn:nbn:de:0030-drops-99989
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9998/
Go to the corresponding LIPIcs Volume Portal

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

Stabbing Pairwise Intersecting Disks by Five Points

pdf-format:
LIPIcs-ISAAC-2018-50.pdf (0.7 MB)

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.

BibTeX - Entry

@InProceedings{harpeled_et_al:LIPIcs:2018:9998,
  author =	{Sariel Har-Peled and Haim Kaplan and Wolfgang Mulzer and Liam Roditty and Paul Seiferth and Micha Sharir and Max Willert},
  title =	{{Stabbing Pairwise Intersecting Disks by Five Points}},
  booktitle =	{29th International Symposium on Algorithms and Computation  (ISAAC 2018)},
  pages =	{50:1--50:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-094-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{123},
  editor =	{Wen-Lian Hsu and Der-Tsai Lee and Chung-Shou Liao},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9998},
  URN =		{urn:nbn:de:0030-drops-99989},
  doi =		{10.4230/LIPIcs.ISAAC.2018.50},
  annote =	{Keywords: Disk graph, piercing set, LP-type problem}
}

Keywords: Disk graph, piercing set, LP-type problem
Collection: 29th International Symposium on Algorithms and Computation (ISAAC 2018)
Issue Date: 2018
Date of publication: 06.12.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI