English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

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 acommon 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 polygonsin 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 $\mathbb{R}^3$, weget 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 polygonsfor 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.

Efficiently stabbing convex polygons and variants of the Hadwiger-Debrunner $(p, q)$-theorem