Skip to Main content Skip to Navigation
Journal articles

The convexification effect of Minkowski summation

Abstract : Let us define for a compact set A⊂Rn the sequence A(k)={(a1+⋯+ak)/k : a1, …, ak ∈ A} = 1/k (A+⋯+A) (k times). It was independently proved by Shapley, Folkman and Starr (1969) and by Emerson and Greenleaf (1969) that A(k) approaches the convex hull of A in the Hausdorff distance induced by the Euclidean norm as k goes to ∞. We explore in this survey how exactly A(k) approaches the convex hull of A, and more generally, how a Minkowski sum of possibly different compact sets approaches convexity, as measured by various indices of non-convexity. The non-convexity indices considered include the Hausdorff distance induced by any norm on Rn, the volume deficit (the difference of volumes), a non-convexity index introduced by Schneider (1975), and the effective standard deviation or inner radius. After first clarifying the interrelationships between these various indices of non-convexity, which were previously either unknown or scattered in the literature, we show that the volume deficit of A(k) does not monotonically decrease to 0 in dimension 12 or above, thus falsifying a conjecture of Bobkov et al. (2011), even though their conjecture is proved to be true in dimension 1 and for certain sets A with special structure. On the other hand, Schneider's index possesses a strong monotonicity property along the sequence A(k), and both the Hausdorff distance and effective standard deviation are eventually monotone (once k exceeds n). Along the way, we obtain new inequalities for the volume of the Minkowski sum of compact sets, falsify a conjecture of Dyn and Farkhi (2004), demonstrate applications of our results to combinatorial discrepancy theory, and suggest some questions worthy of further investigation.
Complete list of metadata

https://hal-upec-upem.archives-ouvertes.fr/hal-03134001
Contributor : Admin Upem <>
Submitted on : Monday, February 8, 2021 - 4:28:24 AM
Last modification on : Monday, March 22, 2021 - 1:24:06 PM

Links full text

Identifiers

Citation

Matthieu Fradelizi, Mokshay Madiman, Arnaud Marsiglietti, Artem Zvavitch. The convexification effect of Minkowski summation. EMS Surveys in Mathematical Sciences, EMS Publishing House, 2018, 5 (1/2), pp.1-64. ⟨10.4171/EMSS/26⟩. ⟨hal-03134001⟩

Share

Metrics

Record views

31