Efficiently Stabbing Convex Polygons and Variants of the Hadwiger-Debrunner (p, q)-Theorem

Abstract

Hadwiger and Debrunner showed that for families of convex sets in R^dwith 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( log log n)^1/3+ np²) expected time. For polyhedra in R³, we get an algorithm running in O((p − q + 1)n^5/2log¹⁰n(log log 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 R^d× Z^kor abstract convex geometries.