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^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/3 log⁸ 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/2 log¹⁰ 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^k or abstract convex geometries.