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.

Date

Aug 11, 2021

Event

Location

Online