Home Bookmarks Papers Blog

Minimum Convex Partitions and Maximum Empty Polytopes

Adrian Dumitrescu, Sariel Har-Peled, and Csaba D. Tóth.

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