A Variant of the Hadwiger-Debrunner (p, q)-Problem in the Plane

作者：Govindarajan Sathish^*; Nivasch Gabriel

来源：Discrete & Computational Geometry, 2015, 54(3): 637-646.

DOI：10.1007/s00454-015-9723-9

• Convex set
• Transversal
• Hadwiger-Debrunner (p, q)-problem
• Weak epsilon-net
• Helly's theorem
• Fractional Helly

Let X be a convex curve in the plane (say, the unit circle), and let be a family of planar convex bodies such that every two of them meet at a point of X. Then has a transversal of size at most . Suppose instead that only satisfies the following "(p, 2)-condition": Among every p elements of , there are two that meet at a common point of X. Then has a transversal of size . For comparison, the best known bound for the Hadwiger-Debrunner (p, q)-problem in the plane, with , is . Our result generalizes appropriately for if is, for example, the moment curve.

• 出版日期2015-10