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


Hadwiger and Debrunner showed that for families of convex sets in Rd 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)n4/3 log8 n(log log n)1/3 + np2) expected time. For polyhedra in R3, we get an algorithm running in O((p−q+ 1)n5/2 log10 n(log log n)1/6 + np3) 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 Rd×Zk or abstract convex geometries.

Proceedings of the 33rd Canadian Conference on Computational Geometry, CCCG 2021, August 10-12, 2021, Dalhousie University, Halifax, Nova Scotia, Canada
Justin Dallant
Justin Dallant
PhD Student in Computer Science