Efficiently stabbing convex polygons and variants of the Hadwiger-Debrunner (p, q)-theorem

2020/02/17 by Justin Dallant, Dallant, Justin, Patrick Schnider +1
Computer Science · Mathematics · #Computational Geometry and Mesh Generation #Digital Image Processing Techniques #Point processes and geometric inequalities

paper · pdf · doi:10.48550/arxiv.2002.06947

Abstract

Hadwiger and Debrunner showed that for families of convex sets in ℝ^d with the property that among any p of them some q have a common point, the whole family can be stabbed with p-q+1 points if p ≥ q ≥ d+1 and (d-1)p < d(q-1). This generalizes a classical result by Helly. We show how such a stabbing set can be computed for a family of convex polygons in the plane with a total of n vertices in O((p-q+1)n^4/3log⁸ n(loglog n)^1/3 + np²) expected time. For polyhedra in ℝ³, we get an algorithm running in O((p-q+1)n^5/2log¹⁰ n(loglog n)^1/6 + np³) expected time. We also investigate other conditions on convex polygons for which our algorithm can find a fixed number of points stabbing them. Finally, we show that analogous results of the Hadwiger and Debrunner (p,q)-theorem hold in other settings, such as convex sets in ℝ^d×ℤ^k or abstract convex geometries.

Related

• New results on stabbing segments with a polygon
• A new lower bound on Hadwiger-Debrunner numbers in the plane
• On Piercing Numbers of Families Satisfying the (p,q)_r Property
• Convex Polygon Containment: Improving Quadratic to Near Linear Time
• Improved bounds on the Hadwiger-Debrunner numbers