On the quality of randomized approximations of Tukey's depth

Simon Briend, Gábor Lugosi, Roberto Imbuzeiro Oliveira

Tukey's depth (or halfspace depth) is a widely used measure of centrality for multivariate data. However, exact computation of Tukey's depth is known to be a hard problem in high d…