From a (p, 2)-Theorem to a Tight (p, q)-Theorem

Chaya Keller, Shakhar Smorodinsky

نتاج البحث: فصل من :كتاب / تقرير / مؤتمرمنشور من مؤتمرمراجعة النظراء

ملخص

A family F of sets is said to satisfy the (p, q)-property if among any p sets of F some q have a nonempty intersection. The celebrated (p, q)-theorem of Alon and Kleitman asserts that any family of compact convex sets in ℝd that satisfies the (p, q)-property for some q ≥ d + 1, can be pierced by a fixed number (independent on the size of the family) fd(p, q) of points. The minimum such piercing number is denoted by HDd(p, q). Already in 1957, Hadwiger and Debrunner showed that whenever q > d-1/d p + 1 the piercing number is HDd(p, q) = p - q + 1; no exact values of HDd(p, q) were found ever since. While for an arbitrary family of compact convex sets in ℝd, d ≥ 2, a (p, 2)-property does not imply a bounded piercing number, such bounds were proved for numerous specific families. The best-studied among them is axis-parallel boxes in ℝd, and specifically, axis-parallel rectangles in the plane. Wegner (1965) and (independently) Dol'nikov (1972) used a (p, 2)-theorem for axis-parallel rectangles to show that HDrect(p, q) = p - q + 1 holds for all q > √2p. These are the only values of q for which HDrect(p, q) is known exactly. In this paper we present a general method which allows using a (p, 2)-theorem as a bootstrapping to obtain a tight (p, q)-theorem, for families with Helly number 2, even without assuming that the sets in the family are convex or compact. To demonstrate the strength of this method, we show that HDd-box(p, q) = p - q + 1 holds for all q > c'logd-1 p, and in particular, HDrect(p, q) = p - q + 1 holds for all q ≥ 7 log2 p (compared to q ≥ √2p, obtained by Wegner and Dol'nikov more than 40 years ago). In addition, for several classes of families, we present improved (p, 2)-theorems, some of which can be used as a bootstrapping to obtain tight (p, q)-theorems. In particular, we show that any family F of compact convex sets in ℝd with Helly number 2 admits a (p, 2)-theorem with piercing number O(p2d-1), and thus, satisfies HDF(p, q) = p - q + 1 for all q > cp1-1/2d-1, for a universal constant c.

اللغة الأصليةالإنجليزيّة
عنوان منشور المضيف34th International Symposium on Computational Geometry, SoCG 2018
المحررونCsaba D. Toth, Bettina Speckmann
ناشرSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
الصفحات511-5114
عدد الصفحات4604
رقم المعيار الدولي للكتب (الإلكتروني)9783959770668
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 1 يونيو 2018
الحدث34th International Symposium on Computational Geometry, SoCG 2018 - Budapest, هنغاريا
المدة: ١١ يونيو ٢٠١٨١٤ يونيو ٢٠١٨

سلسلة المنشورات

الاسمLeibniz International Proceedings in Informatics, LIPIcs
مستوى الصوت99

!!Conference

!!Conference34th International Symposium on Computational Geometry, SoCG 2018
الدولة/الإقليمهنغاريا
المدينةBudapest
المدة١١/٠٦/١٨١٤/٠٦/١٨

All Science Journal Classification (ASJC) codes

  • !!Software

بصمة

أدرس بدقة موضوعات البحث “From a (p, 2)-Theorem to a Tight (p, q)-Theorem'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا