Let S be a set of n points in d-space.
A convex Steiner partition is a tiling of CH(S) with
empty convex bodies. For every integer d, we show that
S admits a convex Steiner partition with at most
tiles. This bound is the best possible for affine independent
points in the plane, and it is best possible apart from constant
factors in every dimension d>= 3. We also give the first
constant-factor approximation algorithm for computing a minimum
Steiner convex partition of an affine independent point set in
the plane. Determining the maximum possible volume of a single
tile in a Steiner partition is equivalent to a famous problem
of Danzer and Rogers. We give a (1-µ)-approximation
for the maximum volume of an empty convex body when S
lies in the d-dimensional unit box [0,1]d.
Last modified: Sun Dec 4 22:50:45 CST 2011