Tukey depth (or halfspace depth) is a fundamental and robust measure of the centrality of data points in multivariate datasets. For the uniform distribution over a convex body $K \subset \mathbb{R}^d$, determining the Tukey depth of a point can be viewed as a refined version of testing membership in $K$. However, in contrast to the membership problem, the depth computation problem has received relatively little attention in the literature.

In this talk, we propose an efficient algorithm to determine the approximate depth of a point in $K$. In this setting, the superlevel sets of the depth function are precisely the convex floating bodies of $K$. An important aspect of our data structure is the interaction between these bodies and the Hilbert metric – a projectively-invariant complete Finsler metric defined on $K$.