TY - GEN

T1 - Minimum convex partitions and maximum empty polytopes

AU - Dumitrescu, Adrian

AU - Har-Peled, Sariel

AU - Tóth, Csaba D.

N1 - Funding Information:
Dumitrescu is supported in part by the NSF grant DMS-1001667; Har-Peled is supported in part by the NSF grant CCF-0915984; Tóth acknowledges support from the NSERC grant RGPIN 35586.

PY - 2012

Y1 - 2012

N2 - Let S be a set of n points in d-space. A convex Steiner partition is a tiling of conv(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 points in general position in the plane, and it is 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 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) in any dimension d ≥ 2. Here we give a (1 - ∈)- 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 .

AB - Let S be a set of n points in d-space. A convex Steiner partition is a tiling of conv(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 points in general position in the plane, and it is 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 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) in any dimension d ≥ 2. Here we give a (1 - ∈)- 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 .

UR - http://www.scopus.com/inward/record.url?scp=84863110389&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84863110389&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-31155-0_19

DO - 10.1007/978-3-642-31155-0_19

M3 - Conference contribution

AN - SCOPUS:84863110389

SN - 9783642311543

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 213

EP - 224

BT - Algorithm Theory, SWAT 2012 - 13th Scandinavian Symposium and Workshops, Proceedings

T2 - 13th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2012

Y2 - 4 July 2012 through 6 July 2012

ER -