Minimum Convex Partitions and Maximum Empty Polytopes

DOI10.1007/978-3-642-31155-0_19MaRDI QIDQ2904557zbMATH OpenOpenAlexFDO

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

Publication date 14 August 2012

Published in Algorithm Theory – SWAT 2012 (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1112.1124

Mathematics Subject Classification ID

Computational aspects related to convexity (52B55) Tilings in (n) dimensions (aspects of discrete geometry) (52C22) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Abstract: Let $S$ be a set of $n$ points in $mathbb{R}^d$. A Steiner convex partition is a tiling of $mconv(S)$ with empty convex bodies. For every integer $d$, we show that $S$ admits a Steiner convex partition with at most $lceil(n-1)/dceil$ 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 $dgeq3$. 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 convex 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 $omega(1/n)$. Here we give a $(1-varepsilon)$-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$.

Recommendations

• Minimum convex partitions and maximum empty polytopes
• Minimum convex partitions of multidimensional polyhedrons
• A Convex Approach to Minimal Partitions
• Minimum \(d\)-convex partition of a multidimensional polyhedron with holes
• Minimum convex partition of point sets
• scientific article; zbMATH DE number 1440643
• Minimum convex partition of a constrained point set
• On the honeycomb conjecture for a class of minimal convex partitions
• Minimum convex partition of a polygon with holes by cuts in given directions
• Minimum convex partition of a polygon with holes by cuts in given directions

Cited in

(5)

• Minimum convex partitions of multidimensional polyhedrons
• Minimum convex partitions and maximum empty polytopes
• Minimum Perimeter-Sum Partitions in the Plane
• On the honeycomb conjecture for a class of minimal convex partitions
• A Convex Approach to Minimal Partitions

This page was built for publication: Minimum Convex Partitions and Maximum Empty Polytopes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2904557)