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

Justin Dallant,
Patrick Schnider

September 2021

### 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^{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 R^{d}×Z^{k} or abstract convex geometries.

Publication

Proceedings of the 33rd Canadian Conference on Computational Geometry, CCCG 2021, August 10-12, 2021, Dalhousie University, Halifax, Nova Scotia, Canada

###### PhD Student in Computer Science