  Consider a set P of N random points on the unit sphere of dimension $d-1$,
and the symmetrized set S = P union (-P). The halving polyhedron of S is
defined as the convex hull of the set of centroids of N distinct points in S.
We prove that after appropriate rescaling this halving polyhedron is Hausdorff
close to the unit ball with high probability, as soon as the number of points
grows like $Omega(d log(d))$. From this result, we deduce probabilistic lower
bounds on the complexity of approximations of the distance to the empirical
measure on the point set by distance-like functions.
