论文标题
体积helly结果中集合的等距和仿射副本
Isometric and affine copies of a set in volumetric Helly results
论文作者
论文摘要
我们表明，对于任何紧凑型凸套装$ \ mathbb {r}^d $中的$ k $，以及任何有限的家族$ \ nathcal {f} $ cosevex set s in $ \ mathbb {r}^d $，如果每一个充分的$ \ nathcal $ a $ a $ s $ s $ s的相互作用的相互作用，则整个家庭中包含$ k $的等距副本，比例为$（1- \ varepsilon）$，其中$ \ varepsilon $是正面且预先确定的。除非$ k $与磁盘非常相似，否则不可避免的因素是不可避免的。我们证明了$ K $的仿射副本的类似结果。我们展示了我们的结果如何暗示存在随机算法的存在，该算法近似于$ k $的最大副本，该副本适合给定的PoliceTope $ P $，其预期运行时是在$ p $的面上线性的。
We show that for any compact convex set $K$ in $\mathbb{R}^d$ and any finite family $\mathcal{F}$ of convex sets in $\mathbb{R}^d$, if the intersection of every sufficiently small subfamily of $\mathcal{F}$ contains an isometric copy of $K$ of volume $1$, then the intersection of the whole family contains an isometric copy of $K$ scaled by a factor of $(1-\varepsilon)$, where $\varepsilon$ is positive and fixed in advance. Unless $K$ is very similar to a disk, the shrinking factor is unavoidable. We prove similar results for affine copies of $K$. We show how our results imply the existence of randomized algorithms that approximate the largest copy of $K$ that fits inside a given polytope $P$ whose expected runtime is linear on the number of facets of $P$.
