Efficiency of the floating body as a robust measure of dispersion

Among robust notions of shape, depth and dispersion of a distribution or dataset we have Tukey depth and depth curves, which are essentially the same as the convex floating body in convex geometry. These notions are important because they play the role of multidimensional quantiles and rank statistics. At the same time, they can be difficult to use because they are computationally intractable in general. We develop a theory of algorithmic efficiency for these notions for several broad and relevant families of distributions: symmetric log-concave distributions and certain multivariate stable distributions and power-law distributions. As an example of the power of these results, we show how to solve the Independent Component Analysis problem for power-law distributions, even when the first moment is infinite.