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 -