Absolute approximation of Tukey depth: Theory and experiments

Dan Chen

A Monte Carlo approximation algorithm for the Tukey depth problem in moderate dimensions is introduced. The algorithm is a generalization of an algorithm presented by Rousseeuw and Struyf (1998). The performance of this algorithm is studied both analytically, using new results on the combinatorics of arrangements, and experimentally, using test data sets from the UCI Machine Learning Repository.