### Minimum convex partitions and maximum empty polytopes

#### Abstract

Let *S* be a set of *n* points in **R**^{d}. A Steiner convex partition is a tiling of conv(*S*) with empty convex bodies. For every integer *d*, we show that *S* admits a Steiner convex partition with at most ⌈(*n*-1)/*d*⌉ tiles. This bound is the best possible for points in general position in the plane, and it is the best possible apart from constant factors in every fixed dimension *d*≥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 ω(1/*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}.

#### Full Text:

PDFDOI: http://dx.doi.org/10.20382/jocg.v5i1a5

ISSN: 1920-180X