On convex holes in d-dimensional point sets

Abstract: Given a finite set

A s u b s e t e q m a t h b b R^{d}

, points

a_{1}, a_{2}, d o t s c, a_{e l l} i n A

form an

e l l

-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

m a t h b b R^{d}

having no holes of size

O (4^{d} d l o g 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^{7 d}

. The better bound is obtained using a variant of

(t, m, s)

-nets, obeying a relaxed equidistribution condition.

This page was built for publication: On convex holes in $d$-dimensional point sets