Let us define for a compact set $A subset mathbb{R}^n$ the sequence $$ A(k) = left{frac{a_1+cdots +a_k}{k}: a_1, ldots, a_kin Aright}=frac{1}{k}Big(underset{k {rm times}}{underbrace{A + cdots + A}}Big). $$ 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 $infty$. 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 $mathbb{R}^n$, 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, Schneiders 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.
Download