  We present a new fast approximate algorithm for Tukey (halfspace) depth level
sets and its implementation-ABCDepth. Given a $d$-dimensional data set for any
$d\geq 1$, the algorithm is based on a representation of level sets as
intersections of balls in $\mathbb{R}^d$. Our approach does not need
calculations of projections of sample points to directions. This novel idea
enables calculations of approximate level sets in very high dimensions with
complexity which is linear in $d$, which provides a great advantage over all
other approximate algorithms. Using different versions of this algorithm we
demonstrate approximate calculations of the deepest set of points ("Tukey
median") and Tukey's depth of a sample point or out-of-sample point, all with a
linear in $d$ complexity. An additional theoretical advantage of this approach
is that the data points are not assumed to be in "general position". Examples
with real and synthetic data show that the executing time of the algorithm in
all mentioned versions in high dimensions is much smaller than the time of
other implemented algorithms. Also, our algorithms can be used with thousands
of multidimensional observations.
