On the planar spherical depth and lens depth

For a distribution function F on R^d and a point q ∈ R^d, the spherical depth SphD(q; F) is defined to be the probability that a point q is contained inside a random closed hyperball obtained from a pair of points from F. The lens depth LD(q; F) is defined analogously using hyperlens instead of hyperball in the definition of spherical depth. The spherical depth SphD(q; S) (lens depth LD(q; S)) is also defined for an arbitrary data set S ⊆ R^d and point q ∈ R^d. This definition is based on counting all of the closed hyperballs (hyper-lenses), obtained from pairs of points in S, that contain q. The straightforward algorithm for computing the spherical depth (lens depth) in dimension d takes O(dn²). The main result of this paper is an optimal algorithm for computing the planar (bivariate) spherical depth. The algorithm takes O(n log n) time. By reducing the problem of Element Uniqueness, we prove that computing the spherical depth (lens depth) requires Ω(n log n) time. Some geometric properties of spherical depth (lens depth) are also investigated in this paper. These properties indicate that simplicial depth (SD) is linearly bounded by spherical depth and lens depth (in particular, LD ≥ SphD ≥ 3² SD). To illustrate these relationships, some experimental results are provided. In these experiments on random point sets, the bounds of SphD ≥ 2 SD and LD ≥ 1.2 SphD are achieved.