Minimum convex partitions and maximum empty polytopes

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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 .

Original languageEnglish (US)
Title of host publicationAlgorithm Theory, SWAT 2012 - 13th Scandinavian Symposium and Workshops, Proceedings
Number of pages12
StatePublished - 2012
Event13th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2012 - Helsinki, Finland
Duration: Jul 4 2012Jul 6 2012

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7357 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other13th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2012

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Minimum convex partitions and maximum empty polytopes'. Together they form a unique fingerprint.

Cite this