# An Optimal Algorithm for Computing the Spherical Depth of Points in the
Plane

David Bremner and Rasoul Shahsavarifar
Faculty of Computer Science
University of New Brunswick
Fredericton, NB, Canada
Email:{bremner, ra.shahsavari} @unb.ca

#### Abstract.

For a distribution function $F$ on $\mathbb{R}^{d}$ and a point
$q\in\mathbb{R}^{d}$, the _spherical depth_
$\operatorname{\textit{SphD}}(q;F)$ is defined to be the probability that a
point $q$ is contained inside a random closed hyper-ball obtained from a pair
of points from $F$. The spherical depth $\operatorname{\textit{SphD}}(q;S)$ is
also defined for an arbitrary data set $S\subseteq\mathbb{R}^{d}$ and
$q\in\mathbb{R}^{d}$. This definition is based on counting all of the closed
hyper-balls, obtained from pairs of points in $S$, that contain $q$. The
significant advantage of using the spherical depth in multivariate data
analysis is related to its complexity of computation. Unlike most other data
depths, the time complexity of the spherical depth grows linearly rather than
exponentially in the dimension $d$. The straightforward algorithm for
computing the spherical depth in dimension $d$ takes $O(dn^{2})$. The main
result of this paper is an optimal algorithm that we present for computing the
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
requires $\Omega(n\log n)$ time. Some geometric properties of spherical depth
are also investigated in this paper. These properties indicate that
_simplicial depth_ ($\operatorname{\textit{SD}}$) (Liu, 1990) is linearly
bounded by spherical depth (in particular,
$\operatorname{\textit{SphD}}\geq\frac{2}{3}SD$). To illustrate this
relationship between the spherical depth and the simplicial depth, some
experimental results are provided. The obtained experimental bound
($\operatorname{\textit{SphD}}\geq 2\operatorname{\textit{SD}}$) indicates
that, perhaps, a stronger theoretical bound can be achieved.

##  1 Introduction

The rank statistic tests play an important role in univariate non-parametric
statistics. If one attempts to generalize the rank tests to the multivariate
case, the problem of defining a multivariate order statistic will occur. It is
not clear how to define a multivariate order or rank statistic in a meaningful
way. One approach to overcome this problem is to use the notion of data depth.
Data depth measures the centrality of a point in a given data set in non-
parametric multivariate data analysis. In other words, it indicates how deep a
point is located with respect to the data set.

Over the last decades, various notions of data depth such as _halfspace depth_
(Hotelling, 1929, [3, 8]; Tukey, 1975, [9]), _simplicial depth_ (Liu, 1990,
[5]) _Oja depth_ (Oja, 1983, [7]), and others have emerged as powerful tools
for non-parametric multivariate data analysis. Most of them have been defined
to solve specific problems in data analysis. They are different in
application, definition, and geometry of their central regions (regions with
the maximum depth).

In 2006, Elmore, Hettmansperger, and Xuan [2] defined another notion of data
depth named _spherical depth_. It is defined as the probability that point $q$
is contained in a closed random hyper-ball with the diameter
$\overline{x_{i}x_{j}}$, where $x_{i}$ and $x_{j}$ are two random points from
a common distribution function $F$. These closed hyper-balls are known as
influence regions of the spherical depth function. The concept of sphere area
is the multidimensional generalization of _Gabriel circles_ in the definition
of the _Gabriel Graph_ [6]. Spherical depth has some nice properties including
affine invariance, symmetry, maximality at the centre and monotonicity. All of
these properties are explored in [2] and [10].

A notable characteristic of the spherical depth is that its time complexity
grows linearly in dimension $d$ while for most other data depths the time
complexity grows exponentially. To the best of our knowledge, the current best
algorithm for computing the spherical depth is the straightforward algorithm
which takes $O(n^{2})$.

In this paper, we present an $O(n\log n)$ algorithm for computing the
spherical depth in $\mathbb{R}^{2}$. Furthermore, we reduce the problem of
Element Uniqueness111Element Uniqueness problem: Given a set
$A=\\{a_{1},a_{2},...,a_{n}\\}$, is there a pair of indices $i,j$ with $i\neq
j$ such that $a_{i}=a_{j}$? to prove that computing the spherical depth of a
query point requires $\Omega(n\log n)$ time. We also investigate some
geometric properties of spherical depth. These properties lead us to bound the
simplicial depth of a point in terms of the spherical depth. Finally, some
experiments are provided to illustrate the relationship between spherical
depth and simplicial depth.

##  2 Spherical depth

#### Definition:

The spherical influence region, also called sphere area, of $x_{i}$ and
$x_{j}$ in $\mathbb{R}^{d}$ ($Sph(x_{i},x_{j})$) is a closed hyperball with
the diameter $\overline{x_{i}x_{j}}$. In other words,

$\forall(i,j):Sph(x_{i},x_{j})=\left\\{t\mid
d(t,\frac{x_{i}+x_{j}}{2})\leq\frac{d(x_{i},x_{j})}{2}\right\\},$

where $d(.,.)$ is the Euclidean distance. Figure 2 shows the sphere area
formed by two points $x_{i}$ and $x_{j}$, $Sph(x_{i},x_{j})$, in
$\mathbb{R}^{2}$.

#### Definition:

For a distribution function $F$ on $\mathbb{R}^{d}$, the spherical depth
function of $q\in\mathbb{R}^{d}$ is defined as the probability that $q$ is
contained within the sphere area $\operatorname{\textit{Sph}}(x_{i},x_{j})$ of
two random vectors $x_{i}$ and $x_{j}$ from $F$. This definition can be
represented by (1).

$\operatorname{\textit{SphD}}(q;F)=P(q\in Sph(x_{i},x_{j}))$ (1)

#### Definition:

Let $S=\\{x_{1},...,x_{n}\\}$ be a set of points in $\mathbb{R}^{d}$.
$\operatorname{\textit{SphD}}(q;S)$, the spherical depth of a point
$q\in\mathbb{R}^{d}$ with respect to $S$, is defined as a proportion of the
sphere areas of $\operatorname{\textit{Sph}}(x_{i},x_{j}),1\leq i<j\leq n$
that contain $q$. Using the indicator function I, this definition can be
represented by (2).

$\operatorname{\textit{SphD}}(q;S)=\frac{1}{{n\choose 2}}\sum_{1\leq i<j\leq
n}^{n}{I(q\in\operatorname{\textit{Sph}}(x_{i},x_{j})})$ (2)

Figure 2 shows the spherical depth of an arbitrary point $q\in\mathbb{R}^{2}$
with respect to $S=\\{p_{1},p_{2},p_{3}\\}$.

Figure 1: Spherical depth of the points in the plane

Figure 2: _Sphere area defined by $x_{i}$ and $x_{j}$_

###  2.1 Algorithm for Computing the Spherical Depth of a Query Point

The current best algorithm for computing the spherical depth of a point
$q\in\mathbb{R}^{d}$ with respect to a data set
$S=\\{x_{1},x_{2},...,x_{n}\\}\subseteq\mathbb{R}^{d}$ is the brute force
algorithm. This naive algorithm needs to check all of the $n\choose 2$ sphere
areas obtained from the data points to figure out how many of them contain
$q$. It can be verified that $q$ is contained in the sphere area
$\operatorname{\textit{Sph}}(x_{i},x_{j})$ if and only if $d(x_{i},x_{j})\geq
2d(q,c)$, where $x_{i}$ and $x_{j}$ are two arbitrary points from $S$, and
$c=(x_{i}+x_{j})/2$ is the center of
$\operatorname{\textit{Sph}}(x_{i},x_{j})$. See Figure 2 for an illustration
in $\mathbb{R}^{2}$. Checking all of the sphere areas causes the naive
algorithm to take $\Theta(dn^{2})$. Instead of counting, we focus on the
geometric aspects of the sphere areas. These geometric properties lead us to
develop an $O(n\log n)$ algorithm (Algorithm 1) for the computation of the
spherical depth of $q$.

######  Lemma 2.1.

For arbitrary points $a$, $b$, and $t$ in $\mathbb{R}^{2}$,
$t\in\operatorname{\textit{Sph}}(a,b)$ if and only if $\angle
atb\geq\frac{\pi}{2}$.

###### Proof.

If $t$ is on the boundary of $\operatorname{\textit{Sph}}(a,b)$, the
_Inscribed Angle Theorem_ (Theorem $2.2$ in [4]) suffices as the proof in both
directions. For the rest of the proof, by
$t\in\operatorname{\textit{Sph}}(a,b)$, we mean $t\in
int\>\operatorname{\textit{Sph}}(a,b)$.

$\Rightarrow$) For $t\in\operatorname{\textit{Sph}}(a,b)$, suppose that
$\angle atb<\frac{\pi}{2}$ (proof by contradiction). We continue the line
segment $\overline{at}$ to cross the boundary of the
$\operatorname{\textit{Sph}}(a,b)$. Let $t^{\prime}$ be the crossing point
(see Figure 4). Since $\angle atb<\frac{\pi}{2}$, then, $\angle btt^{\prime}$
is greater than $\frac{\pi}{2}$. Let $\angle
btt^{\prime}=\frac{\pi}{2}+\epsilon_{1};\epsilon_{1}>0$. From the Inscribed
Angle Theorem, we know that $\angle at^{\prime}b$ is a right angle. The angle
$tbt^{\prime}=\epsilon_{2}>0$ because $t\in\operatorname{\textit{Sph}}(a,b)$.
Summing up the angles in $\bigtriangleup tt^{\prime}b$, as computed in (3),
leads to a contradiction. So, this direction of proof is complete.

$\angle tt^{\prime}b+\angle t^{\prime}bt+\angle
btt^{\prime}\geq\frac{\pi}{2}+\epsilon_{2}+(\frac{\pi}{2}+\epsilon_{1})=\pi+\epsilon_{1}+\epsilon_{2}>\pi$
(3)

$\Leftarrow$) If $\angle atb=\frac{\pi}{2}+\epsilon_{1};\epsilon_{1}>0$, we
prove that $t\in\operatorname{\textit{Sph}}(a,b)$. Suppose that
$t\notin\operatorname{\textit{Sph}}(a,b)$ (proof by contradiction). Since
$t\notin\operatorname{\textit{Sph}}(a,b)$, at least one of the line segments
$\overline{at}$ and $\overline{bt}$ crosses the boundary of
$\operatorname{\textit{Sph}}(a,b)$. Without loss of generality, assume that
$\overline{at}$ is the one that crosses the boundary of
$\operatorname{\textit{Sph}}(a,b)$ at the point $t^{\prime}$ (see Figure 4).
Considering the Inscribed Angle Theorem, we know that $\angle
at^{\prime}b=\frac{\pi}{2}$ and consequently, $\angle
bt^{\prime}t=\frac{\pi}{2}$. The angle $\angle t^{\prime}bt=\epsilon_{2}>0$
because $t\notin\operatorname{\textit{Sph}}(a,b)$. If we sum up the angles in
the triangle $\bigtriangleup tt^{\prime}b$, the same contradiction as in (3)
will be implied. ∎

Figure 3: $t$ inside $\operatorname{\textit{Sph}}(a,b)$

Figure 4: $t$ outside $\operatorname{\textit{Sph}}(a,b)$

#### Algorithm:

Using Lemma 2.1, we present an algorithm to compute the spherical depth of a
query point $q\in\mathbb{R}^{2}$ with respect to
$S=\\{x_{1},x_{2},...,x_{n}\\}\subseteq\mathbb{R}^{2}$. This algorithm is
summarized in the following steps.

  * •

Translating the points: Suppose that $T$ is a translation by $(-q)$. We apply
$T$ to translate $q$ and all data points into their new coordinates.
Obviously, $T(q)=0$.

Figure 5: Transferred and sorted data set $S_{T}$ obtained from $S$

  * •

Sorting the translated data points: In this step we sort the translated data
points based on their angles in their polar coordinates. After doing this
step, we have $S_{T}$ which is a sorted array of the translated data points.
See Figure 5.

  * •

Calculating the spherical depth: Suppose that $x_{i}(r_{i},\theta_{i})$ is the
$i^{th}$ element in $S_{T}$. For $x_{i}$, we define the arrays $O_{i}$ and
$N_{i}$ as follows:

$O_{i}=\left\\{j\mid x_{j}\in
S_{T}\>,\frac{\pi}{2}\leq|\theta_{i}-\theta_{j}|\leq\frac{3\pi}{2}\right\\}$
$N_{i}=\\{1,2,...,n\\}\setminus O_{i}.$

Thus the spherical depth of the origin of the coordinate system with respect
to the data set $S_{T}$, which is equivalent to the spherical depth of $q$
with respect to $S$, can be computed by:

$\operatorname{\textit{SphD}}(q;S)=\operatorname{\textit{SphD}}(T(q);S_{T})=\operatorname{\textit{SphD}}(0;S_{T})=\frac{1}{2}\sum_{1\leq
i\leq n}|O_{i}|,$

where $|O_{i}|$ is the length of $O_{i}$. To present an formula for computing
the $|O_{i}|$, we define $f_{i}$ and $l_{i}$ as follows:

$f_{i}=\begin{cases}\min N_{i}-1&\text{if
$\frac{\pi}{2}<\theta_{i}\leq\frac{3\pi}{2}$}\\\ \min
O_{i}&\text{otherwise}\end{cases}$

$l_{i}=\begin{cases}\max N_{i}+1&\text{if
$\frac{\pi}{2}<\theta_{i}\leq\frac{3\pi}{2}$}\\\ \max
O_{i}&\text{otherwise.}\end{cases}$

Figure 7 illustrates $O_{i}$, $N_{i}$, $f_{i}$, and $l_{i}$ in two different
cases. Considering the definitions of $f_{i}$ and $l_{i}$,

$|O_{i}|=\begin{cases}f_{i}+(n-l_{i}+1)&\text{if
$\frac{\pi}{2}<\theta_{i}\leq\frac{3\pi}{2}$}\\\
l_{i}-f_{i}+1&\text{otherwise.}\end{cases}$

Figure 6: Two representations of $S_{T}$ for
$\theta\in(\frac{\pi}{2},\frac{3\pi}{2}].$

Figure 7: Two representations of $S_{T}$ for
$\theta\notin(\frac{\pi}{2},\frac{3\pi}{2}].$

#### Time complexity:

To analyse the time complexity of the algorithm, we need to compute the time
complexities of the procedures in the algorithm (see the pseudocode of the
algorithm in Algorithm 1). The first procedure takes $O(n)$ to translate $q$
and all data points into the new coordinate system. The second procedure takes
$O(n\log n)$ time. In this procedure, the loop iterates $n$ times, and the
sorting algorithm takes $O(n\log n)$. Due to using the binary search algorithm
for every $O_{i}$, the running time of the last procedure is also $O(n\log
n)$. The rest of the algorithm contributes some constant time. In total, the
running time of the algorithm is $O(n\log n)$.

Algorithm 1 Computing the spherical depth of points in the plane

1:A data set $S$ and a query point $q$

2:Spherical Depth of $q$ with respect to $S$
($\operatorname{\textit{SphD}}(q;S)$)

3:

4:procedure Translating points

5:input: $S$

6:output: Translated data set ($S_{T}$)

7: for each $x_{i}\in S$ do

8: $x_{i}\leftarrow(x_{i}-q)$

9: return $S_{T}$

10:

11:procedure Sorting translated data points around $T(q)$

12:input: $S_{T}$ and $T(q)$

13:output: Sorted array $S_{TP}$

14: for each $x_{i}\in S_{T}$ do

15: $x_{i}\leftarrow$ Polar coordinate of $x_{i}$ // $x_{i}(\theta_{i},r_{i})$
is obtained here.

16: Using an $O(n\log n)$ sorting algorithm, sort $x_{i}$ based on
$\theta_{i}$

17: return $S_{TP}$

18:

19:procedure Depth calculation

20:input: $S_{TP}$

21:output: Depth value of $\operatorname{\textit{SphD}}(q;S)$

22: for each $x_{i}\in S_{TP}$ do

23: $O_{i}\leftarrow\left\\{j\mid x_{j}\in
S_{TP}\>,\frac{\pi}{2}\leq|\theta_{i}-\theta_{j}|\leq\frac{3\pi}{2}\right\\}$

24: $N_{i}\leftarrow\\{1,2,\dots,n\\}\setminus O_{i}$

25: Using two _binary search calls_ , find the elements $f_{i}$ and $l_{i}$ in
$S_{TP}$.

26: $f_{i}=\begin{cases}\min N_{i}-1&\text{if
$\frac{\pi}{2}<\theta_{i}\leq\frac{3\pi}{2}$}\\\ \min
O_{i}&\text{otherwise}\end{cases}$

27:

28: $l_{i}=\begin{cases}\max N_{i}+1&\text{if
$\frac{\pi}{2}<\theta_{i}\leq\frac{3\pi}{2}$}\\\ \max
O_{i}&\text{otherwise.}\end{cases}$

29:

30: Compute $|O_{i}|=\begin{cases}f_{i}+(n-l_{i}+1);&\text{if
$\frac{\pi}{2}<\theta_{i}\leq\frac{3\pi}{2}$}\\\
l_{i}-f_{i}+1;&\text{otherwise.}\end{cases}$

31: $\operatorname{\textit{SphD}}(q;S)\leftarrow\frac{1}{2}\sum_{1\leq i\leq
n}|O_{i}|$

32: return $\operatorname{\textit{SphD}}(q;S)$

33:

34:End;

##  3 Lower Bound for Computing the Spherical Depth of a Point in the Plane

We reduce the problem of Element Uniqueness to the problem of computing the
spherical depth. It is known that the question of Element Uniqueness has a
lower bound of $\Omega(n\log n)$ in the algebraic decision tree model of
computation [1].

######  Theorem 3.1.

Computing the spherical depth of a query point in the plane takes
$\Omega(n\log n)$ time.

###### Proof.

We show that finding the spherical depth allows us to answer the question of
Element Uniqueness. Suppose that $A=\\{a_{1},a_{2},...,a_{n}\\}$, for $n\geq
2$ is a given set of real numbers.222Note: We suppose all of the $a_{i}$s to
be only positive(negative), otherwise we partition $A$ into two sets $A_{1}$
(consisting of only positive numbers) and $A_{2}$ (consisting of only negative
numbers), and prove the theorem for $A_{1}$ and $A_{2}$, separately. Note that
$A=A_{1}\cup A_{2}$ and $A_{1}\cap A_{2}=\emptyset$. For every $a_{i}\in A$ we
construct four points $x_{i}$, $x_{n+i}$, $x_{2n+i}$, and $x_{3n+i}$ in the
polar coordinate system as follows:

$x_{i}=\left(r_{i},\theta_{i}\right),\>x_{n+i}=\left(r_{i},\theta_{i}+\frac{\pi}{2}\right),\>x_{2n+i}=\left(r_{i},\theta_{i}+\pi\right),\>\text{and}\>x_{3n+i}=\left(r_{i},\theta_{i}+\frac{3\pi}{2}\right),$

where $r_{i}=\sqrt{1+{a_{i}^{2}}}$ and $\theta_{i}=\tan^{-1}(1/a_{i})$. Thus
we have a set $S$ of $4n$ points $x_{i}$, $x_{n+i}$, $x_{2n+i}$, and
$x_{3n+i}$, for $1\leq i\leq n$. See Figure 8.

We select the query point $q=(0,0)$, and define $O_{j}$ as follows:

$O_{j}=\left\\{x_{k}\in S\mid\angle
x_{j}qx_{k}\geq\frac{\pi}{2}\right\\},\>1\leq j\leq 4n.$ (4)

We compute $\operatorname{\textit{SphD}}(q;S)$ in order to answer the Element
Uniqueness problem. Suppose that $x_{j}\in S$, for $1\leq j\leq 4n$, is a
unique element. In this case, $|O_{j}|=2n+1$ because, from (4), it can be
figured out that the expanded $O_{j}$ is as follows:

$O_{j}=\begin{cases}\\{x_{n+1},...,x_{n+j},x_{2n+1},...,x_{3n},x_{3n+j},...,x_{4n}\\};&\text{if
$j\in\\{1,...,n\\}$}\\\
\\{x_{2n+1},...,x_{n+j},x_{3n+1},...,x_{4n},x_{j-n},...,x_{n}\\};&\text{if
$j\in\\{n+1,...,2n\\}$}\\\
\\{x_{3n+1},...,x_{j+n},x_{1},...,x_{n},x_{j-n},...,x_{2n}\\};&\text{if
$j\in\\{2n+1,...,3n\\}$}\\\
\\{x_{1},...,x_{j-3n},x_{n+1},...,x_{2n},x_{j-n},...,x_{3n}\\};&\text{otherwise.}\end{cases}$

Figure 8: A representation of $A$ (determined by red points) $S$ (determined
by blue points) and duplications in these sets

Referring to Lemma 2.1 and Algorithm 1,

$\operatorname{\textit{SphD}}(q;S)=\frac{1}{2}\sum_{1\leq j\leq
4n}|O_{j}|=\frac{1}{2}\sum_{1\leq j\leq
4n}(2n+1)=\frac{1}{2}(4n)(2n+1)=4n^{2}+2n$

Now suppose that there exist some $i\neq j$ with $x_{i}=x_{j}$ in $S$. In this
case, from (4), it can be seen that

$\displaystyle|O_{i}|=|O_{j}|=|O_{(n+i)\bmod 4n}|=|O_{(n+j)\bmod
4n}|=|O_{(2n+i)\bmod 4n}|=$ $\displaystyle|O_{(2n+j)\bmod 4n}|=|O_{(3n+i)\bmod
4n}|=|O_{(3n+j)\bmod 4n}|=2n+2.$

See Figure 8. Lemma 2.1 and Algorithm 1 imply that

$\displaystyle\operatorname{\textit{SphD}}(q;S)=\frac{1}{2}\sum_{1\leq j\leq
4n}|O_{j}|=\frac{1}{2}((4n-8)(2n+1)+8(2n+2))=4n^{2}+2n+4.$

Thus if some element is duplicated in $S$, $\operatorname{\textit{SphD}}(q;S)$
is strictly higher than if $S$ has no repetition in its elements. In other
words, the question of Element Uniqueness can be answered by finding the
spherical depth. Therefore the elements of $A$ are unique if and only if the
spherical depth of $(0,0)$ with respect to $S$ is $4n^{2}+2n$. This implies
that the computation of spherical depth require $\Omega(n\log n)$ time. It is
necessary to mention that the only computations in the reduction are the
construction of $S$ that take $O(n)$ time. ∎

##  4 Relationships Between Spherical Depth and Simplicial Depth

#### Definition:

For a point $q\in\mathbb{R}^{2}$ and a data set $S$ consisting of $n$ points
in $\mathbb{R}^{2}$, we define $\operatorname{\textit{Bin}}(q;S)$ to be the
set of all closed sphere areas, out of $n\choose 2$ possible sphere areas,
that contain $q$. We also define $\operatorname{\textit{Sin}}(q;S)$ to be the
set of all closed simplices, out of $n\choose 3$ possible closed simplices
defined by $S$, that contain $q$.

######  Lemma 4.1.

Suppose that $q$ is a point in a given convex hull $H$ obtained from a data
set $S$ in $\mathbb{R}^{2}$. $q$ is covered by the union of sphere areas
defined by $S$.

###### Proof.

It can be seen that there is at least one triangle, defined by the vertices of
$H$, that contains $q$. We prove that the union of the sphere areas defined by
such triangle contains $q$. See Figure 10 and Figure 10. We prove this
statement by contradiction. Suppose that $q$ is covered by none of
$\operatorname{\textit{Sph}}(a,b)$, $\operatorname{\textit{Sph}}(a,c)$, and
$\operatorname{\textit{Sph}}(b,c)$. Therefore, Lemma 2.1 implies that none of
the angles $\angle aqb$, $\angle aqc$, and $\angle bqc$ is greater than or
equal to $\frac{\pi}{2}$ which is a contradiction because at least one of
these angles should be at least $\frac{2\pi}{3}$ in order to get $2\pi$ as
their sum. ∎

######  Lemma 4.2.

Suppose that $S=\\{a,b,c\\}$ is a set of points in $\mathbb{R}^{2}$. For every
$q\in\mathbb{R}^{2}$, if $|\operatorname{\textit{Sin}}(q;S)|=1$, then
$|\operatorname{\textit{Bin}}(q;S)|\geq 2$.

Another form of Lemma 4.2 is that if $q\in\bigtriangleup abc$, then $q$ falls
inside at least two sphere areas out of three sphere areas
$\operatorname{\textit{Sph}}(a,b)$, $\operatorname{\textit{Sph}}(c,b)$, and
$\operatorname{\textit{Sph}}(a,c)$. The equivalency between these two forms of
the lemma is clear. We prove just the first one.

Figure 9: Convex hull $H$ contains point $q$.

Figure 10: Triangle $abc$ contains point $q$.

###### Proof.

We prove the lemma by contradiction. By Lemma 4.1,
$\operatorname{\textit{Bin}}(q;S)\geq 1$. Suppose that
$|\operatorname{\textit{Bin}}(q;S)|=1$. If $q$ is located on the vertices of
$\bigtriangleup abc$, it clear that $|\operatorname{\textit{Bin}}(q;S)|\geq 2$
thus, we suppose that $q$ is not located on the vertices of $\bigtriangleup
abc$. Without loss of generality, we suppose that $q$ falls inside the
$\operatorname{\textit{Sph}}(a,b)$. For the rest of the proof, we focus on the
relationships among the angles $\angle aqb$, $\angle cqa$, and $\angle cqb$
(see Figure 10). Since $q$ is inside $\bigtriangleup abc$, $\angle
aqb\leq\pi$. Consequently, at least one of $\angle cqa$ and $\angle cqb$ is
greater than or equal to $\frac{\pi}{2}$. So, Lemma 2.1 implies that $q$ will
fall inside at least one of the $\operatorname{\textit{Sph}}(a,c)$ and
$\operatorname{\textit{Sph}}(b,c)$. Hence,
$|\operatorname{\textit{Bin}}(q;S)|=1$ contradicts
$|\operatorname{\textit{Sin}}(q;S)|=1$. This means that the case
$|\operatorname{\textit{Bin}}(q;S)|\geq 2$. As an illustration, in Figure 10,
for the points inside the hatched area $|\operatorname{\textit{Bin}}(q;S)|=3$.
∎

######  Lemma 4.3.

For $S=\\{x_{1},...,x_{n}\\}\subset\mathbb{R}^{2}$,
$\frac{|\operatorname{\textit{Bin}}(q;S)|}{|\operatorname{\textit{Sin}}(q;S)|}\geq\frac{2}{n-2}$.

###### Proof.

We suppose that
$\operatorname{\textit{Sph}}(x_{i},x_{j})\in\operatorname{\textit{Bin}}(q;S)$
(see Figure 11). There exist at most $(n-2)$ triangles in
$\operatorname{\textit{Sin}}(q;S)$ such that $x_{i}x_{j}$ is an edge of them.
Let us consider $\bigtriangleup x_{i}x_{j}x_{k}$ from these triangles.
Referring to Lemma 4.2, we know that $q$ falls inside at least one of
$\operatorname{\textit{Sph}}(x_{i},x_{k})$ and
$\operatorname{\textit{Sph}}(x_{j},x_{k})$. It means that there exist at most
$(n-2)$ triangles in $\operatorname{\textit{Sin}}(q;S)$ such that $x_{i}x_{k}$
(respectively $x_{j}x_{k}$) is an edge of them. As can be seen, the triangle
$\bigtriangleup x_{i}x_{j}x_{k}$ is counted at least two times, one time for
$\operatorname{\textit{Sph}}(x_{i},x_{j})$ and one time for
$\operatorname{\textit{Sph}}(x_{i},x_{k})$ (or
$\operatorname{\textit{Sph}}(x_{j},x_{k})$ ). So, we can say that for every
sphere area from $\operatorname{\textit{Bin}}(q;S)$, such as
$\operatorname{\textit{Sph}}(x_{i},x_{j})$ there exist at most
$\frac{(n-2)}{2}$ distinct triangles, triangles with only one common side, in
$\operatorname{\textit{Sin}}(q;S)$. Consequently, (5) can be obtained.

$\frac{(n-2)}{2}|\operatorname{\textit{Bin}}(q;S)|\geq|\operatorname{\textit{Sin}}(q;S)|\Rightarrow\frac{|\operatorname{\textit{Bin}}(q;S)|}{|\operatorname{\textit{Sin}}(q;S)|}\geq\frac{2}{(n-2)}$
(5)

∎

Figure 11: Sphere area $\operatorname{\textit{Sph}}(x_{i},x_{j})$ contains
point $q$

######  Theorem 4.4.

For $q\in\mathbb{R}^{2}$ and a given data set $S$ which consists of $n$ points
in $\mathbb{R}^{2}$,
$\operatorname{\textit{SphD}}(q;S)\geq\frac{2}{3}\operatorname{\textit{SD}}(q;S)$.

###### Proof.

From the definitions of spherical depth and simplicial depth, we can calculate
the ratio of
$\frac{\operatorname{\textit{SphD}}(q;S)}{\operatorname{\textit{SD}}(q;S)}$ as
follows:

$\frac{\operatorname{\textit{SphD}}(q;S)}{\operatorname{\textit{SD}}(q;S)}=\frac{\frac{|\operatorname{\textit{Bin}}(q;S)|}{{n\choose
2}}}{\frac{|\operatorname{\textit{Sin}}(q;S)|}{{n\choose
3}}}=\frac{|\operatorname{\textit{Bin}}(q;S)|}{|\operatorname{\textit{Sin}}(q;S)|}\times\frac{(n-2)}{3}$
(6)

From (6) and Lemma 4.3, it can be seen that

$\frac{\operatorname{\textit{SphD}}(q;S)}{\operatorname{\textit{SD}}(q;S)}\geq\frac{2}{3}\Rightarrow\operatorname{\textit{SphD}}(q;S)\geq\frac{2}{3}\operatorname{\textit{SD}}(q;S).$

∎

##  5 Experiments

To support Theorem 4.4, we compute the spherical depth and the simplicial
depth of the points in three random sets $Q_{1}$, $Q_{2}$, and $Q_{3}$ with
respect to data sets $S_{1}$, $S_{2}$, and $S_{3}$, respectively. The elements
of $Q_{i}$ and $S_{i}$ are some randomly generated points (double precision
floating point) within the square $A=\\{(x,y)|x,y\in[-10,10]\\}$. The results
of our experiments are summarized in Table 1. Every cell in the table
represents the corresponding depth of $q_{i}$ with respect to data set
$S_{i}$, where $q_{i}\in Q_{i}$. The cardinalities of $Q_{i}$s and $S_{i}$s
are as follows: $|Q_{1}|=100$, $|S_{1}|=750$, $|Q_{2}|=750$, $|S_{2}|=2500$,
$|Q_{3}|=2500$, $|S_{3}|=10000$.

As can be seen in Table 1, the experimental results are consistent with
Theorem 4.4. In fact, the experimental results suggest a bound that is
stronger than the obtained bound in Theorem 4.4. This difference between the
experimental bound and the theoretical bound is a motivation to do more
research in this area.

| $(q_{1};S_{1})$ | $(q_{2};S_{2})$ | $(q_{3};S_{3})$
---|---|---|---
| Min | Max | Min | Max | Min | Max
$\operatorname{\textit{SD}}$ | 0.00 | 0.25 | 0 | 0.25 | 0.00 | 0.24
$\operatorname{\textit{SphD}}$ | 0.01 | 0.50 | 0.00 | 0.50 | 0.00 | 0.50
$\frac{\operatorname{\textit{SphD}}}{\operatorname{\textit{SD}}}$ | 2.00 | $\infty$ | 2.00 | $\infty$ | 2.02 | $\infty$
Table 1: Minimum and Maximum of
simplicial depth, spherical depth, and
the ratio of these data depths.

##  6 Conclusion

In this paper, we developed an optimal $\Theta(n\log n)$ algorithm to compute
the spherical depth of a bivariate query point with respect to a given data
set in $\mathbb{R}^{2}$. To obtain a lower bound for the algorithm, the
Element Uniqueness problem, which requires $\Omega(n\log n)$ time, is reduced
to the computing of spherical depth. In addition to the time complexity, the
main advantage of this algorithm is it simplicity for implementation. We also
investigated some geometric properties which lead us to find a theoretical
relationship (i.e. $\operatorname{\textit{SphD}}\geq\frac{2}{3}SD$) between
the spherical depth and the simplicial depth. Finally, some experimental
results which suggest a stronger bound (i.e. $\operatorname{\textit{SphD}}\geq
2SD$) are provided. More research on this topic is needed to figure out if the
real bound is closer to the experimental bound or to the current theoretical
bound.

## References

  * [1] Ben-Or, Michael. Lower bounds for algebraic computation trees, Proceedings of the fifteenth annual ACM symposium on Theory of computing. Vol. 2, 80-86, 1983.
  * [2] Elmore, Ryan T and Hettmansperger, Thomas P and Xuan, Fengjuan. Spherical data depth and a multivariate median, Journal of ”DIMACS Series in Discrete Mathematics and Theoretical Computer Science”. Vol. 72, 87-101,2006.
  * [3] Hotelling, Harold. Stability in competition, The Collected Economics Articles of Harold Hotelling. Springer, 50-63, 1990.
  * [4] Libeskind, Shlomo. Euclidean and transformational geometry: A deductive inquiry. Vol. 2, 523-531,2008.
  * [5] Liu, Regina Y and others. On a notion of data depth based on random simplices. Journal of ”The Annals of Statistics”, Vol. 18, 405-414, 1990.
  * [6] Liu, Zhenyu and Modarres, Reza. Lens data depth and median. Journal of Nonparametric Statistics, Vol. 23, 1063-1974, 2011.
  * [7] Oja, Hannu. Descriptive statistics for multivariate distributions. Journal of Statistics & Probability Letters, Vol. 1, 327-332, 1983.
  * [8] Small, Christopher G. A survey of multidimensional medians, Journal of ”International Statistical Review/Revue Internationale de Statistique”, 263-277,1990.
  * [9] Tukey, John W. Proceedings of the international congress of mathematicians. Vol. 2, 523-531,1975.
  * [10] Yang, Mengta. Depth Functions, Multidimensional Medians and Tests of Uniformity on Proximity Graphs. PhD Thesis, The George Washington University, 2014.