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 \geq q \geq 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 n convex polygons of constant size in the plane  in O((p-q+1)n^{4/3}\log^{ 2  + \epsilon (n ) + p^2\log(p) ) expected time. For convex polyhedra in R^3, the method yields an algorithm running in O((p-q+1)n^{ 13/ 5 +\epsilon }  n(\log\log n)^{1/6} } + p^4 ) expected time. We also  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.
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 \geq q \geq 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 + np^2 ) expected time. For polyhedra in R^3, we get an algorithm running in O((p-q+1)n^{ 5 /2 } \log^{10 n(\log\log n)^{1/6} } + np^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.
R
n convex polygons of constant size
a family of convex polygons
A
with a total of n vertices
R
2
8
A
n(\log\log n)^{1/3
D
\epsilon
R
(n
np^2
D
+ p^2\log(p) )
D
convex
R
the method yields
we get
D
13/
R
+\epsilon
/2
A
\log^{10
R
p^4
np^3
A
investigate other conditions on convex polygons for which our algorithm can find a fixed number of points stabbing them. Finally, we