  The computational complexity of some depths that satisfy the projection
property, such as the halfspace depth or the projection depth, is known to be
high, especially for data of higher dimensionality. In such scenarios, the
exact depth is frequently approximated using a randomized approach: The data
are projected into a finite number of directions uniformly distributed on the
unit sphere, and the minimal depth of these univariate projections is used to
approximate the true depth. We provide a theoretical background for this
approximation procedure. Several uniform consistency results are established,
and the corresponding uniform convergence rates are provided. For elliptically
symmetric distributions and the halfspace depth it is shown that the obtained
uniform convergence rates are sharp. In particular, guidelines for the choice
of the number of random projections in order to achieve a given precision of
the depths are stated.
