论文标题
在$ D $维点套件中的凸孔
On convex holes in $d$-dimensional point sets
论文作者
论文摘要
Given a finite set $A \subseteq \mathbb{R}^d$, points $a_1,a_2,\dotsc,a_{\ell} \in A$ form an $\ell$-hole in $A$ if they are the vertices of a convex polytope which contains no points of $A$ in its interior.我们在$ \ mathbb {r}^d $中构建任意大点集，没有大小$ o（4^dd \ log d）$或更多的孔。这改善了由于valtr引起的先前已知的上限$ d^{d+o（d）} $。我们构造的基本版本使用某种类型的等分分配点集，源自数值分析，称为$（t，m，s）$ - nets或$（t，s）$ - 序列，产生$ 2^{7d} $的界限。使用$（t，m，s）$ - 网的变体获得更好的界限，遵守轻松的等均分配条件。
Given a finite set $A \subseteq \mathbb{R}^d$, points $a_1,a_2,\dotsc,a_{\ell} \in A$ form an $\ell$-hole in $A$ if they are the vertices of a convex polytope which contains no points of $A$ in its interior. We construct arbitrarily large point sets in general position in $\mathbb{R}^d$ having no holes of size $O(4^dd\log d)$ or more. This improves the previously known upper bound of order $d^{d+o(d)}$ due to Valtr. The basic version of our construction uses a certain type of equidistributed point sets, originating from numerical analysis, known as $(t,m,s)$-nets or $(t,s)$-sequences, yielding a bound of $2^{7d}$. The better bound is obtained using a variant of $(t,m,s)$-nets, obeying a relaxed equidistribution condition.
