Minimum Convex Partitions and Maximum Empty Polytopes

Let $S$ be a set of $n$ points in ${\mathbb{R}}^d$. A Steiner convex partition is a tiling of $\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{v}(S)$ with empty convex bodies. For every integer $d$, we show that $S$ admits a Steiner convex partition with at most $\lceil (n-1)/d\rceil$ tiles. This bound is the best possible for points in general position in the plane, and it is best possible apart from constant factors in every fixed dimension $d\ge 3$. We also give the first constant-factor approximation algorithm for computing a minimum Steiner convex partition of a planar point set in general position. Establishing a tight lower bound for the maximum volume of a tile in a Steiner convex partition of any $n$ points in the unit cube is equivalent to a famous problem of Danzer and Rogers. It is conjectured that the volume of the largest tile is $\omega (1\mathrm{/}n)$. Here we give a $(1-\epsilon )$-approximation algorithm for computing the maximum volume of an empty convex body amidst $n$ given points in the $d$-dimensional unit box $[0,1{]}^d$.