On convex holes in $d$-dimensional point sets

Abstract

Given a finite set $A\subseteq {\mathbb{R}}^d$, points $a_1,a_2,\dots ,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^{d}d\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.

10 pages, 1 figure, improved construction