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

Sathish Govindarajan, Gabriel Nivasch

نتاج البحث: نشر في مجلةمقالةمراجعة النظراء

8 اقتباسات (Scopus)

ملخص

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

اللغة الأصليةالإنجليزيّة
الصفحات (من إلى)637-646
عدد الصفحات10
دوريةDiscrete and Computational Geometry
مستوى الصوت54
رقم الإصدار3
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 7 أكتوبر 2015

بصمة

أدرس بدقة موضوعات البحث “A Variant of the Hadwiger–Debrunner (p, q)-Problem in the Plane'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا