Stabbing Pairwise Intersecting Disks by Four Points

被引:0
作者
Paz Carmi
Matthew J. Katz
Pat Morin
机构
[1] Ben-Gurion University of the Negev,Department of Computer Science
[2] Carleton University,School of Computer Science
关键词
Disks in the plane; Helly-type theorems; Piercing set; 52C10; 68U05;
D O I
暂无
中图分类号
学科分类号
摘要
In their seminal work, Danzer (Stud. Sci. Math. Hungar. 21(1–2), 111–134 (1986)) and Stachó (Mat. Lapok 32(1–3), 19–47 (1981–84)) established that every set D of pairwise intersecting disks in the plane can be stabbed by four points. Recently, Har-Peled et al. (Discrete Math. 344(7), # 112403 (2021)) presented a relatively simple linear-time algorithm for finding five points that stab D. We present an alternative (somewhat less involved) proof to the assertion that four points are sufficient to stab D. Moreover, our proof is constructive and provides a simple linear-time algorithm for finding the stabbing points. As a warmup, we present a nearly-trivial linear-time algorithm with an elementary proof for finding five points that stab D.
引用
收藏
页码:1751 / 1784
页数:33
相关论文
共 15 条
  • [1] Chazelle B(1996)On linear-time deterministic algorithms for optimization problems in fixed dimension J. Algorithms 21 579-597
  • [2] Matoušek J(1986)Zur Lösung des Gallaischen Problems über Kreisscheiben in der Euklidischen Ebene Stud. Sci. Math. Hungar. 21 111-134
  • [3] Danzer L(1959)On intersections of similar sets Portugal. Math. 18 155-164
  • [4] Grünbaum B(1955)Ausgewählte Einzelprobleme der kombinatorischen Geometrie in der Ebene Enseign. Math. 1 56-89
  • [5] Hadwiger H(1923)Über Mengen konvexer Körper mit gemeinschaftlichen Punkten Jahresber. Dtsch. Math.-Ver. 32 175-176
  • [6] Debrunner H(1930)Über Systeme von abgeschlossenen Mengen mit gemeinschaftlichen Punkten Monatsh. Math. Phys. 37 281-302
  • [7] Helly E(2010)Largest bounding box, smallest diameter, and related problems on imprecise points Comput. Geom. 43 419-433
  • [8] Helly E(1996)A subexponential bound for linear programming Algorithmica 16 498-516
  • [9] Löffler M(1921)Mengen konvexer Körper, die einen gemeinsamen Punkt enthalten Math. Ann. 83 113-115
  • [10] van Kreveld MJ(1965)Über ein Problem für Kreisscheibenfamilien Acta Sci. Math. (Szeged) 26 273-282