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
(n-1)/d
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}.
Postscript,
PDF.
Last modified: Sun Dec 4 22:50:45 CST 2011