Document Open Access Logo

Stabbing Pairwise Intersecting Disks by Five Points

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

PDF

File

Thumbnail PDF
PDF
LIPIcs.ISAAC.2018.50.pdf
  • Filesize: 0.72 MB
  • 12 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Combinatorics
Keywords
  • Disk graph
  • piercing set
  • LP-type problem

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

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.

Cite As Get BibTex

Sariel Har-Peled, Haim Kaplan, Wolfgang Mulzer, Liam Roditty, Paul Seiferth, Micha Sharir, and Max Willert. Stabbing Pairwise Intersecting Disks by Five Points. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 50:1-50:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.ISAAC.2018.50

Author Details

Sariel Har-Peled
  • Department of Computer Science, University of Illinois, Urbana, IL 61801, USA
Haim Kaplan
  • School of Computer Science, Tel Aviv University, Tel Aviv 69978, Israel
Wolfgang Mulzer
  • Institut für Informatik, Freie Universität Berlin, 14195 Berlin, Germany
Liam Roditty
  • Department of Computer Science, Bar Ilan University, Ramat Gan 5290002, Israel
Paul Seiferth
  • Institut für Informatik, Freie Universität Berlin, 14195 Berlin, Germany
Micha Sharir
  • School of Computer Science, Tel Aviv University, Tel Aviv 69978, Israel
Max Willert
  • Institut für Informatik, Freie Universität Berlin, 14195 Berlin, Germany

Funding

Work on this paper was supported in part by grant 1367/2016 from the German-Israeli Science Foundation (GIF).
  • Har-Peled, Sariel: Partially supported by a NSF AF awards CCF-1421231, and CCF-1217462.
  • Mulzer, Wolfgang: Partially supported by DFG grant MU/3501/1 and ERC STG 757609.
  • Seiferth, Paul: Partially supported by DFG grant MU/3501/1.
  • Sharir, Micha: Partially supported by ISF Grant 892/13, by the Israeli Centers of Research Excellence (I-CORE) program (Center No. 4/11), by the Blavatnik Research Fund in Computer Science at Tel Aviv University, and by the Hermann Minkowski-MINERVA Center for Geometry at Tel Aviv University.

References

  1. Noga Alon and Daniel J. Kleitman. Piercing convex sets and the Hadwiger-Debrunner (p,q)-problem. Adv. Math., 96(1):103-112, 1992. Google Scholar
  2. Timothy M. Chan. An optimal randomized algorithm for maximum Tukey depth. In Proc. 15th Annu. ACM-SIAM Sympos. Discrete Algorithms (SODA), pages 430-436, 2004. Google Scholar
  3. Bernard Chazelle. The Discrepancy Method - Randomness and Complexity. Cambridge University Press, Cambridge, 2001. Google Scholar
  4. Bernard Chazelle and Jiřı Matoušek. On linear-time deterministic algorithms for optimization problems in fixed dimension. J. Algorithms, 21(3):579-597, 1996. Google Scholar
  5. Ludwig Danzer. Zur Lösung des Gallaischen Problems über Kreisscheiben in der Euklidischen Ebene. Studia Sci. Math. Hungar., 21(1-2):111-134, 1986. Google Scholar
  6. Adrian Dumitrescu and Minghui Jiang. Piercing translates and homothets of a convex body. Algorithmica, 61(1):94-115, 2011. Google Scholar
  7. Branko Grünbaum. On intersections of similar sets. Portugal. Math., 18:155-164, 1959. Google Scholar
  8. Hugo Hadwiger and Hans Debrunner. Ausgewählte Einzelprobleme der kombinatorischen Geometrie in der Ebene. Enseignement Math. (2), 1:56-89, 1955. Google Scholar
  9. Eduard Helly. Über Mengen konvexer Körper mit gemeinschaftlichen Punkten. Jahresbericht der Deutschen Mathematiker-Vereinigung, 32:175-176, 1923. Google Scholar
  10. Eduard Helly. Über Systeme von abgeschlossenen Mengen mit gemeinschaftlichen Punkten. Monatshefte für Mathematik, 37(1):281-302, 1930. Google Scholar
  11. Johann Radon. Mengen konvexer Körper, die einen gemeinsamen Punkt enthalten. Mathematische Annalen, 83(1):113-115, 1921. Google Scholar
  12. Raimund Seidel. Small-Dimensional Linear Programming and Convex Hulls Made Easy. Discrete Comput. Geom., 6:423-434, 1991. Google Scholar
  13. Micha Sharir and Emo Welzl. A combinatorial bound for linear programming and related problems. Proc. 9th Sympos. Theoret. Aspects Comput. Sci. (STACS), pages 567-579, 1992. Google Scholar
  14. Lajos Stachó. Über ein Problem für Kreisscheibenfamilien. Acta Sci. Math. (Szeged), 26:273-282, 1965. Google Scholar
  15. Lajos Stachó. A solution of Gallai’s problem on pinning down circles. Mat. Lapok, 32(1-3):19-47, 1981/84. Google Scholar
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact