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 ${\mathbb{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\ge q\ge 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 }^{8}n(\log \log n{)}^{1/3}+n{p}^2)$ expected time. For polyhedra in ${\mathbb{R}}^3$, we get an algorithm running in $O((p-q+1)n^{5/2}{\log }^{10}n(\log \log n{)}^{1/6}+n{p}^3)$ 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 ${\mathbb{R}}^d\times {\mathbb{Z}}^k$ or abstract convex geometries.