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/
Har-Peled, Sariel ;
Kaplan, Haim ;
Mulzer, Wolfgang ;
Roditty, Liam ;
Seiferth, Paul ;
Sharir, Micha ;
Willert, Max
Stabbing Pairwise Intersecting Disks by Five Points
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 |