论文标题
有效地刺入Hadwiger-Debrunner $（P，Q）$ - 定理的凸音多边形和变体
Efficiently stabbing convex polygons and variants of the Hadwiger-Debrunner $(p, q)$-theorem
论文作者
论文摘要
Hadwiger和DeBrunner表明，对于$ \ Mathbb {r}^d $中的凸家族的家庭，其中任何$ p $中的任何$ q $都有一个共同点，可以用$ p-q+1 $点刺入，如果$ p-p \ geq q \ geq q \ geq q \ geq q \ geq d+1 $ 1 $和$（d-1 $和$（d-1 $ and $）p <d（d-d-1）p <d d（q-d（q-1））$。这概括了Helly的经典结果。我们展示了如何为$ o（（（p-q + 1）n $ n^{4/3} \ log^{8} n（\ log log \ log \ log \ log \ log n）^{1/3} + np^2）$ o（（p-q + 1）n $ o（（p-q + 1）n $ o（（p-q + 1）np^{1/3} + np^2）$预期的时间，如何计算凸出多边形的家族。对于$ \ Mathbb {r}^3 $中的Polyhedra，我们在$ O（（P-Q + 1）N^{5/2} \ log^{10} n（\ log \ log \ log \ log n）^{1/6} + np^3）$ o（（p-q + 1）n^{5/2} \ log^{10} + np^3）$预期时间。我们还研究了凸多边形的其他条件，我们的算法可以找到固定数量的刺入点。最后，我们表明，Hadwiger和DeBrunner $（P，Q）$的类似结果 - 定理在其他设置中保留，例如$ \ Mathbb {r}^d \ times \ times \ times \ mathbb {z}^k $或摘要convex geimetries中的convex集。
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 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 $\mathbb{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.
