# Approximate Data Depth Revisited

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

###### Abstract

Halfspace depth and $\beta$-skeleton depth are two types of depth functions in
nonparametric data analysis. The halfspace depth of a query point
$q\in\mathbb{R}^{d}$ with respect to $S\subset\mathbb{R}^{d}$ is the minimum
portion of the elements of $S$ which are contained in a halfspace which passes
through $q$. For $\beta\geq 1$, the $\beta$-skeleton depth of $q$ with respect
to $S$ is defined to be the total number of _$\beta$ -skeleton influence
regions_ that contain $q$, where each of these influence regions is the
intersection of two hyperballs obtained from a pair of points in $S$. The
$\beta$-skeleton depth introduces a family of depth functions that contain
_spherical depth_ and _lens depth_ if $\beta=1$ and $\beta=2$, respectively.
The main results of this paper include approximating the planar halfspace
depth and $\beta$-skeleton depth using two different approximation methods.
First, the halfspace depth is approximated by the $\beta$-skeleton depth
values. For this method, two dissimilarity measures based on the concepts of
_fitting function_ and _Hamming distance_ are defined to train the halfspace
depth function by the $\beta$-skeleton depth values obtaining from a given
data set. The goodness of this approximation is measured by a function of
error values. Secondly, computing the planar $\beta$-skeleton depth is reduced
to a combination of some range counting problems. Using existing results on
range counting approximations, the planar $\beta$-skeleton depth of a query
point is approximated in $O(n\;poly(1/\varepsilon,\log n))$, $\beta\geq 1$.
Regarding the $\beta$-skeleton depth functions, it is also proved that this
family of depth functions converge when $\beta\to\infty$. Finally, some
experimental results are provided to support the proposed method of
approximation and convergence of $\beta$-skeleton depth functions.

#### Keywords:

Data Depth, Halfspace Depth, $\beta$-skeleton Depth, Approximation,
$\varepsilon$-approximation, Fitting Functions, Range Query, Partially Ordered
Sets.

##  1 Introduction

Data depth is a method to generalize the concept of rank in the univariate
data analysis to the multivariate case. Data depth measures the centrality of
a data point with respect to a dataset, and it gives a center-outward ordering
of data points. In other words, applying a data depth on a dataset generates a
partial ordered set (poset) of the data points. A poset is a set together with
a partial ordering relation which is reflexive, antisymmetric and transitive.
Over the last decades various notions of data depth such as _halfspace depth_
(Hotelling [14, 27]; Tukey [29]), _simplicial depth_ (Liu [18]) _Oja depth_
(Oja [20]), _regression depth_ (Rousseeuw and Hubert [21]), and others have
been introduced in the area of non-parametric multivariate data analysis.
These depth functions are different in application, definition, complexity of
computations. Among different notions of data depth, we focus on halfspace
depth and a recently defined data depth named $\beta$-skeleton depth (Yang and
Modarres [31]).

In 1975, Tukey generalized the definition of univariate median and defined the
halfspace median as a point in which the halfspace depth is maximized, where
the halfspace depth is a multivariate measure of centrality of data points.
Halfspace depth is also known as Tukey depth or location depth. In general,
the halfspace depth of a query point $q$ with respect to a given data set $S$
is the smallest portion of data points that are contained in a closed
halfspace through $q$ [5, 29]. The halfspace depth function has various
properties such as vanishing at infinity, affine invariance, and decreasing
along rays. These properties are proved in [9]. Many different algorithms for
the computation of halfspace depth in lower dimensions have been developed
elsewhere [5, 6, 7, 23]. The bivariate and trivariate case of halfspace depth
can be computed exactly in $O(n\log n)$ and $O(n^{2}\log n)$ time [22, 28],
respectively. However, computing the halfspace depth of a query point with
respect to a data set of size $n$ in dimension $d$ is an NP-hard problem if
both $n$ and $d$ are part of the input [15]. Due to the hardness of the
problem, designing efficient algorithms to compute (or approximate) the
halfspace depth of a point remains an interesting task in the research area of
data depth [1, 4, 8, 13].

In 2017, Yang and Modarres introduced a familly of depth functions called
$\beta$-skeleton depth, indexed by a single parameter $\beta\geq 1$. The
$\beta$-skeleton depth of a query point $q\in\mathbb{R}^{d}$ with respect to a
given data set $S$ is defined as the portion of $\beta$-skeleton influence
regions that contain $q$. The influence regions of $\beta$-skeleton depth are
the multidimensional generalization of lunes in the definition of the _$\beta$
-skeleton graph_ [16]. A notable characteristic of the $\beta$-skeleton depth
is related to its time complexity that grows linearly in the dimension $d$
whereas no polynomial algorithms (in the dimension) in higher dimensions are
known for most other data depths. To the best of our knowledge, the current
best algorithm for computing the $\beta$-skeleton depth in higher dimension
$d$ is the straightforward algorithm which takes $\Theta(dn^{2})$. The
authors, in their previous work [25], improved this bound for the planar
$\beta$-skeleton depth. They developed an $O(n^{3/2+\epsilon})$ algorithm for
all values of $\beta\geq 1$, and a $\theta(n\log n)$ algorithm for the special
case of $\beta=1$. Spherical depth (Elmore, Hettmansperger, and Xuan [10]) and
lens depth (Liu and Modarres [19] can be obtained from $\beta$-skeleton depth
by considering $\beta=1$ and $\beta=2$, respectively. It is proved that the
$\beta$-skeleton depth function is monotonic, maximized at the center, and
vanishing at infinity. The $\beta$-skeleton depth function is also
orthogonally (affinely) invariant if the Euclidean (Mahalanobis) distance is
used to construct the $\beta$-skeleton influence regions [10, 19, 30, 31].

The concept of data depth is widely studied by statisticians and computational
geometers. Some directions that have been considered by researchers include
defining new depth functions, improving the complexity of computations,
computing both exact and approximate depth values, and computing depth
functions in higher dimensions. Two surveys by Aloupis [2] and Small [27] can
be referred as overviews of data depth from a computational geometer’s and a
statistician’s point of view, respectively.

In this paper, different methods are presented to approximate the halfspace
and $\beta$-skeleton depth functions. Computing the $\beta$-skeleton depth is
reduced to a combination of range counting problems. Using different range
counting approximations in [3, 12, 26], the planar $\beta$-skeleton depth
($\beta\geq 1$) of a given point is approximated in
$O(n\>poly(1/\varepsilon,\log n))$ query time. Furthermore, we propose an
approximation technique to approximate the halfspace depth using the
$\beta$-skeleton depth. In this method, two dissimilarity measures based on
the concepts of _fitting function_ and _Hamming distance_ are defined to train
the halfspace depth function by the $\beta$-skeleton depth values obtaining
from a given data set. The goodness of approximation can be measured by the
sum of square of error values. We also show that $\beta$-skeleton depth
functions converge when $\beta\rightarrow\infty$. Finally, some experimental
results are provided regarding our proposed method of approximation.

##  2 Halfspace Depth

#### Definition:

The halfspace depth of a query point $q\in\mathbb{R}^{d}$ with respect to a
given data set $S=\\{x_{1},...,x_{n}\\}\subseteq\mathbb{R}^{d}$ is defined as
the minimum portion of points of $S$ contained in any closed halfspace that
has $q$ on its boundary. Using the notation of
$\operatorname{\textit{HD}}(q;S)$, the above definition can be presented by
(1).

$\operatorname{\textit{HD}}(q;S)=\frac{2}{n}\min\\{|S\cap
H|:H\in\mathbb{H},q\in H\\},$ (1)

where $2/n$ is the normalization factor222Instead of the normalization factor
$1/n$ which is common in literature, we use the normalization factor $2/n$ in
order to let the depth of $1$ to be achievable., $\mathbb{H}$ is the class of
all closed halfspaces in $\mathbb{R}^{d}$ that pass through $q$, and $|S\cap
H|$ denotes the number of points within the intersection of $S$ and $H$. As
illustrated in Figure 1, $\operatorname{\textit{HD}}(q_{1};S)=6/13$ and
$\operatorname{\textit{HD}}(q_{1};S)=0$, where $S$ a given set of points in
the plane and $q_{1},q_{2}$ are two query points not in $S$.

Figure 1: Two examples of halfspace depth in the plane

##  3 $\beta$-skeleton Depth

#### Definition:

For $1\leq\beta\leq\infty$, the $\beta$-skeleton influence region of $x_{i}$
and $x_{j}$ ($S_{\beta}(x_{i},x_{j})$) is defined as follows:

$S_{\beta}(x_{i},x_{j})=B(c_{i},r)\cap B(c_{j},r),$ (2)

where $r=\frac{\beta}{2}\|x_{i}-x_{j}\|$,
$c_{i}=\frac{\beta}{2}x_{i}+(1-\frac{\beta}{2})x_{j}$, and
$c_{j}=(1-\frac{\beta}{2})x_{i}+\frac{\beta}{2}x_{j}$.

In the case of $\beta=\infty$, the $\beta$-skeleton influence region is well
defined, and it is a slab defined by two halfspaces. Figure 2 shows the
$\beta$-skeleton influence regions for different values of $\beta$.

Figure 2: The $\beta$-skeleton influence regions defined by $x_{i}$ and
$x_{j}$ for $\beta$=1, 2, 3, and $\beta=\infty$, where
$c=\frac{x_{i}+x_{j}}{2}$, $c_{i}=\frac{3}{2}x_{i}+(1-\frac{3}{2})x_{j}$, and
$c_{j}=(1-\frac{3}{2})x_{i}+\frac{3}{2}x_{j}$

#### Definition:

Let $S=\\{x_{1},...,x_{n}\\}$ be a set of points in $\mathbb{R}^{d}$. For the
parameter $1\leq\beta\leq\infty$, the $\beta$-skeleton depth of a query point
$q\in\mathbb{R}^{d}$ with respect to $S$, is defined as a proportion of the
$\beta$-skeleton influence regions of $S_{\beta}(x_{i},x_{j}),1\leq i<j\leq n$
that contain $q$. Using the indicator function $I$, this definition can be
represented by Equation (3).

$\operatorname{\textit{SkD}}_{\beta}(q;S)=\frac{1}{{n\choose 2}}\sum_{1\leq
i<j\leq n}{I(q\in S_{\beta}(x_{i},x_{j})})$ (3)

It can be verified that $q\in S_{\beta}(x_{i},x_{j})$ is equivalent to the
inequality of
$\frac{\beta}{2}\|x_{i}-x_{j}\|\geq\max\\{\|q-c_{i}\|,\|q-c_{j}\|\\}$, where
$\|c_{i}-c_{j}\|=\|(1-\beta)(x_{i}-x_{j})\|=(\beta-1)\|x_{i}-x_{j}\|$ for
$\beta\geq 1$. The straightforward algorithm for computing the
$\beta$-skeleton depth of $q\in\mathbb{R}^{d}$ takes $\Theta(dn^{2})$ time
because the above inequality should be checked for all $1\leq i,j\leq n$.

##  4 Dissimilarity Measures

In this section, two different types of dissimilarity measures for depth
functions are introduced.

###  4.1 Fitting Functions and Dissimilarity Measures

To determine the dissimilarity between two vectors $U=(u_{1},...,u_{n})$ and
$V=(v_{1},...,v_{n})$, the idea of fitting functions can be applied.
Considering the goodness measures of fitting functions, assume that $f$ is the
best function fitted to $U$ and $V$ which means that
$u_{i}=f(v_{i})\pm\delta_{i}$. Let $\xi_{i}=u_{i}-\overline{U}$, where
$\overline{U}$ is the average of $u_{i}$ ($1\leq i\leq n$). We define the
dissimilarity measure between $U$ and $V$ ($d_{E}(U,V)$) to be a function of
$\delta_{i}$ and $\xi_{i}$ as follows:

$d_{E}(U,V)=1-r^{2},$ (4)

where $r^{2}$ is the coefficient of determination [24] which is defined by:

$r^{2}=\dfrac{\sum\limits_{i=1}^{n}(\xi_{i}^{2}-\delta_{i}^{2})}{\sum\limits_{i=1}^{n}\xi_{i}^{2}}.$
(5)

Since $r^{2}\in[0,1]$, $d_{E}(U,V)\in[0,1]$. A smaller value of $d_{E}(U,V)$
represents more similarity between $U$ and $V$.

#### Definition:

Let $S=\\{x_{1},...,x_{n}\\}$ be a finite set. It is said that $P=(S,\preceq)$
is a partially ordered set (poset) if $\preceq$ is a partial order relation on
$S$, that is, for all $x_{i},x_{j},x_{t}\in S$: $(a)\;x_{i}\preceq x_{i}$;
$(b)\;x_{i}\preceq x_{j}$ and $x_{j}\preceq x_{t}$ implies that $x_{i}\preceq
x_{t}$; $(c)\;x_{i}\preceq x_{j}$ and $x_{j}\preceq x_{i}$ implies that
$x_{i}\equiv_{p}x_{j}$, where $\equiv_{p}$ is the corresponding equivalency
relation.
Poset $P=(S,\preceq)$ is called a chain if any two elements of $S$ are
comparable, i.e., given $x_{i},x_{j}\in S$, either $x_{i}\preceq x_{j}$ or
$x_{j}\preceq x_{i}$. If there is no comparable pair among the elements of
$S$, the corresponding post is an anti chain. Figure 3 illustrates different
posets with the same elements.

Figure 3: Different posets and relations among their elements

###  4.2 Dissimilarity Measures Between two Posets

The idea of defining the following distance comes from the proposed structural
dissimilarity measure between posets in [11]. Let
$\mathbb{P}=\\{P_{t}=(S,\preceq_{t})|t\in\mathbb{N}\\}$ be a finite set of
posets, where $S=\\{x_{1},...,x_{n}\\}$. For $P_{k}\in\mathbb{P}$ we define a
matrix $M^{k}_{n\times n}$ by:

$M^{k}_{ij}=\begin{cases}1\;\;\;\;\;x_{i}\preceq_{k}x_{j}\\\
0\;\;\;\;\;\text{otherwise.}\end{cases}$

We use the notation of $d_{c}(P_{f},P_{g})$ to define a dissimilarity between
two posets $P_{f},P_{g}\in\mathbb{P}$ as follows:

$d_{c}(P_{f},P_{g})=\dfrac{\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}|M^{f}_{ij}-M^{g}_{ij}|}{n^{2}-n}$
(6)

It can be verified that $d_{c}(P_{f},P_{g})\in[0,1]$, where the closer value
to $1$ means the less similarity between $P_{f}$ and $P_{g}$. This measure of
similarity is a metric on $\mathbb{P}$ because for all
$P_{f},P_{g},P_{h}\in\mathbb{P}$,

  * •

$d_{c}(P_{f},P_{g})\geq 0$

  * •

$d_{c}(P_{f},P_{g})=0\Leftrightarrow P_{f}=P_{g}$

  * •

$d_{c}(P_{f},P_{g})=d_{c}(P_{g},P_{f})$

  * •

$d_{c}(P_{f},P_{h})\leq d_{c}(P_{f},P_{g})+d_{c}(P_{g},P_{h}).$

Proving these properties is straightforward. The proof of last property which
is less trivial can be found in Appendix (see Lemma 9.1).

##  5 Approximation of Halfspace Depth

Due to the difficulty of computing the halfspace depth in dimension $d>3$,
many authors have tried to approximate the halfspace depth. We propose a
method to approximate the halfspace depth using another depth function. Among
all depth functions, the $\beta-$skeleton depth is chosen to approximate the
halfspace depth because it is easy to compute and its time complexity, i.e.
$\Theta(dn^{2})$, grows linearly in higher dimension $d$.

###  5.1 Approximation of Halfspace Depth and Fitting Function

Suppose that $S=\\{x_{1},...,x_{n}\\}$ is a set of data points. By choosing
some subsets of $S$ as training samples, we consider the problem of learning
the halfspace depth function using the $\beta-$skeleton depth values. Finally,
by applying the cross validation techniques in machine learning, the best
function $f$ can be obtained such that
$\operatorname{\textit{HD}}(x_{i};S)=f(\operatorname{\textit{SkD}}_{\beta}(x_{i};S))\pm\delta_{i}$.
The function $f$ can be considered as an approximation function for halfspace
depth, where the value of
$d_{E}(\operatorname{\textit{HD}},\operatorname{\textit{SkD}}_{\beta})$ that
can be computed using Equation (4) is the error of approximation.

###  5.2 Approximation of Halfspace Depth and Poset Dissimilarity

In some applications, the structural ranking among the elements of $S$ is more
important than the depth value of single points. Let $S=\\{x_{1},...,x_{n}\\}$
be a set of points and $D$ be a depth function. Applying $D$ on $x_{i}$ with
respect to $S$ generates a poset (in particular, a chain). In fact,
$P_{D}=(D(x_{i};S),\leq)$ is a chain because for every $x_{i},x_{j}\in S$, the
values of $D(x_{i};S)$ and $D(x_{j};S)$ are comparable. For halfspace depth
and $\beta$-skeleton depth, their dissimilarity measure of rankings can be
obtained by Equation (6) as follows:

$d_{c}(\operatorname{\textit{HD}},\operatorname{\textit{SkD}}_{\beta})=\dfrac{\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}|M^{\operatorname{\textit{HD}}}_{ij}-M^{\operatorname{\textit{SkD}}_{\beta}}_{ij}|}{n^{2}-n}.$

The smaller value of
$d_{c}(\operatorname{\textit{HD}},\operatorname{\textit{SkD}}_{\beta})$, the
more similarity between $\operatorname{\textit{HD}}$ and
$\operatorname{\textit{SkD}}_{\beta}$ in ordering the elements of $S$.

In both of the above approximation methods, any other depth function can be
considered instead of $\beta$-skeleton depth to approximate the halfspace
depth.

######  Conjecture 5.1.

For two depth functions $D_{1}$ and $D_{2}$, the small value of
$d_{c}(D_{1},D_{2})$ implies the small value of $d_{E}(D_{1},D_{2})$ and vice
versa.

##  6 Approximation of $\beta$-skeleton Depth

The convergence of $\beta$-skeleton depth functions when $\beta\to\infty$ is
investigated in this section. Furthermore, the problem of planar
$\beta$-skeleton depth is reduced to a combination of disk and halfspace range
counting problems. This reduction is applied to approximate the planar
$\beta$-skeleton depth using the range counting approximation.

###  6.1 Convergence of $\beta$-skeleton Depth Functions

The following theorem helps understand the definition of
$\operatorname{\textit{SkD}}_{\infty}$ in Equation (3).

######  Theorem 6.1.

If $\beta\to\infty$, all $\beta$-skeleton depth functions converge to
$\operatorname{\textit{SkD}}_{\infty}$. In other words, for data set
$S=\leavevmode\nobreak\ \\{x_{1},...,x_{n}\\}$ and query point $q$,

$\lim_{\beta\to\infty}\frac{\operatorname{\textit{SkD}}_{\beta}(q;S)}{\operatorname{\textit{SkD}}_{(\beta+1)}(q;S)}=1.$
(7)

###### Proof.

Referring to (3), the definition of $\beta$-skeleton depth, it is enough to
prove that if $\beta\to\infty$,

$\forall x_{i},x_{j}\in
S;\;S_{\beta}(x_{i},x_{j})=S_{(\beta+1)}(x_{i},x_{j}).$ (8)

It is proved that $S_{\beta}(x_{i},x_{j})\subseteq
S_{(\beta+1)}(x_{i},x_{j})$, and $u_{\beta}=u_{(\beta+1)}$ if $\beta\to\infty$
(see Lemma 9.2 and Lemma 9.3 in Appendix). Since the influence regions of
$\beta$-skeleton depth functions are closed and convex, the proof is complete
if

$\lim_{\beta\to\infty}\frac{A(S_{\beta ij})}{A(S_{(\beta+1)ij})}=1,$ (9)

where $A(S_{\beta ij})$ is the area of $S_{\beta}(x_{i},x_{j})$. It can be
verified that $A(S_{\beta ij})$ is equal to $\theta r^{2}-da$, where
$d=(\beta-1)l$, $a=(\l/2)\sqrt{(2\beta-1)}$, $r=\beta l/2$,
$\theta=\cos^{-1}((\beta-1)/\beta)$, and $l=d(x_{i},x_{j})$. See Figure 4.

Figure 4: An illustration of $d$, $a$, $r$, $l$, and $\theta$.

$\frac{A(S_{\beta
ij})}{A(S_{(\beta+1)ij})}=\frac{\beta^{2}\cos^{-1}[(\beta-1)/\beta]-(\beta-1)\sqrt{2\beta-1}}{(\beta+1)^{2}\cos^{-1}[\beta/(\beta+1)]-\beta\sqrt{2\beta+1}}$

Equation (9) is proved because

$\lim_{\beta\to\infty}\cos^{-1}(\frac{\beta-1}{\beta})=\lim_{\beta\to\infty}\cos^{-1}(\frac{\beta}{\beta+1})=0.$

∎

###  6.2 $\varepsilon-$approximation of Planar $\beta$-skeleton Depth

In this section, we prove that for
$S=\\{x_{1},...,x_{n}\\}\subset\mathbb{R}^{2}$ and $q\in\mathbb{R}^{2}$,
computing $\operatorname{\textit{SkD}}_{\beta}(q;S)$ is equivalent with at
most $3n$ semialgebraic range counting problems. This result can be applied to
approximate the planar $\beta$-skeleton depth in $O(n\>poly(1/\varepsilon,\log
n))$ query time with $O(n\>poly(1/\varepsilon,\log n))$ storage and the same
bound for preprocessing time.

Given a set $S=\\{x_{1},...,x_{n}\\}\subset\mathbb{R}^{2}$, a semialgebraic
range $\tau$ with constant description complexity, and a parameter
$\varepsilon>0$, $S$ can be preprocessed into a data structure that helps to
efficiently compute an approximated count $\eta_{\tau}$ which satisfies the
$(\varepsilon,\tau)$-approximation given by:

$(1-\varepsilon)|S\cap\tau|\leq\eta_{\tau}\leq(1+\varepsilon)|S\cap\tau|.$

Considering $S$ and $\varepsilon$ as introduced above, a short list of latest
results for approximation of some semialgebraic range counting problems in
$\mathbb{R}^{2}$ is as follows.

  * •

Halfspace: With $O(n\>poly(1/\varepsilon,\log n))$ preprocessing time, one can
construct a data structure of size $O(n\>poly(1/\varepsilon,\log n))$ such
that for a given halfspace $\hbar$, it outputs a number $\eta_{\hbar}$ that
satisfies the $(\varepsilon,\hbar)$-approximation with the query time
$O(poly(1/\varepsilon,\log n))$. For points in $\mathbb{R}^{3}$, the same
results can be obtained [12].

  * •

Disk: By standard lifting of planar points to the paraboloid in
$\mathbb{R}^{3}$, one can reduce a disk range query in the plane to a
halfspace range query in three dimensions [12].

  * •

Circular cap: A circular cap is the larger part of a circle cut by a line. In
near linear time, $S$ can be preprocessed into a linear size data structure
that returns the emptiness result of any circular cap query in $O(poly\log
n)$. With $O(\varepsilon^{-2}T(n)\log n)$ preprocessing time and
$O(\varepsilon^{-2}S(n)\log n)$ storage, one can construct a data structure
such that for a given circular cap $\rho$, it returns in
$O(\varepsilon^{-2}Q(n)\log n)$ time, a number $\eta_{\rho}$ that satisfies
the $(\varepsilon,\rho)$-approximation. Both of $T(n)$ and $S(n)$ are near
linear and $Q(n)$ is the emptiness query of $\rho$ [26].

#### Definition:

For an arbitrary non-zero point $a\in\mathbb{R}^{2}$ and parameter $\beta\geq
1$, $\ell(p)$ is a line that is perpendicular to $\overrightarrow{a}$ at the
point $p=p(a,\beta)={(\beta-1)a}/{\beta}$. This line forms two halfspaces
$H_{o}(p)$ and $H_{a}(p)$. The one that includes the origin is $H_{o}(p)$ and
the other one that includes $a$ is $H_{a}(p)$.

#### Definition:

For a disk $B(c,r)$ with the center $c=c(a,\beta)={\beta a}/{(2(\beta-1))}$
and radius $r=\|c\|$, $B_{o}(c,r)$ is the intersection of $H_{o}(p)$ and
$B(c,r)$, and $B_{a}(c,r)$ is the intersection of $H_{a}(p)$ and $B(c,r)$,
where $\beta>1$ and $a$ is an arbitrary non-zero point in $\mathbb{R}^{2}$.

Figure 5 is an illustration of these definitions for different values of
parameter $\beta$.

Figure 5: The $H_{o}(p)$ and $B(c,r)$ defined by $a\in\mathbb{R}^{2}$ for
$\beta=1,\;1.5,\;2,\;\text{and}\;\beta\rightarrow\infty$, where
$A=H_{o}(p)\setminus\\{intB_{o}(c,r)\\}$

######  Theorem 6.2.

For arbitrary non-zero points $a$, $b$ in $\mathbb{R}^{2}$ and parameter
$\beta>1$, $b\in H_{o}(p)\setminus\\{intB_{o}(c,r)\\}$ if and only if the
origin $O=(0,0)$ is contained in $S_{\beta}(a,b)$, where $c={\beta
a}/{(2(\beta-1))}$, $r=\|c\|$, and $p={(\beta-1)a}/{\beta}$.

###### Proof.

First, we show that $B_{o}(c,r)$ is a well-defined set meaning that $\ell(p)$
intersects $B(c,r)$. We compute $d(c,\ell(p))$, the distance of $c$ from
$\ell(p)$, and prove that this value is not greater than $r$. It can be
verified that $d(c,\ell(p))=d(c,p)$. Let $k={\beta}/{(2(\beta-1))}$; the
following calculations complete this part of the proof.

$\displaystyle d(c,p)$ $\displaystyle=d(\frac{\beta
a}{2(\beta-1)},\frac{(\beta-1)a}{\beta})=d(ka,\frac{1}{2k}a)$
$\displaystyle=(k-\frac{1}{2k})\sqrt{({a_{x}}^{2}+{a_{y}}^{2})}=(\frac{2k^{2}-1}{2k})\|a\|$
$\displaystyle\leq\frac{2k^{2}}{2k}\|a\|=k\|a\|=r$

We recall the definition of $\beta$-influence region given by
$S_{\beta}(a,b)=B(c_{a},\frac{\beta}{2}\|a-b\|)\cap
B(c_{b},\frac{\beta}{2}\|a-b\|)$, where
$c_{a}=\frac{\beta}{2}a+(1-\frac{\beta}{2})b$ and
$c_{b}=\frac{\beta}{2}b+(1-\frac{\beta}{2})a$. Using this definition,
following equivalencies can be derived from $O\in S_{\beta}(a,b)$.

$O\in S_{\beta}(a,b)\Leftrightarrow\frac{\beta\|a-b\|}{2}\geq
max\\{\|c_{a}\|,\|c_{b}\|\\}\Leftrightarrow$ $\beta\|a-b\|\geq
max\\{\|\beta(a-b)+2b\|,\|\beta(b-a)+2a\|\\}\Leftrightarrow$
$\beta^{2}\|a-b\|^{2}\geq
max\\{\|\beta(a-b)+2b\|^{2},\|\beta(b-a)+2a\|^{2}\\}$ $\Leftrightarrow 0\geq
max\\{b^{2}(1-\beta)+\beta\overrightarrow{a}.\overrightarrow{b},a^{2}(1-\beta)+\beta\overrightarrow{a}.\overrightarrow{b}\\}.$

By solving these inequalities for $(\beta-1)/\beta$ which is equal to $1/2k$,
we have:

$\frac{1}{2k}\geq
max\left\\{\frac{\overrightarrow{a}.\overrightarrow{b}}{\|a\|^{2}},\frac{\overrightarrow{a}.\overrightarrow{b}}{\|b\|^{2}}\right\\}.$
(10)

For a fixed point $a$, the inequalities in Equation (10) determine one
halfspace and one disk given by (11) and (12), respectively.

$\frac{1}{2k}\geq\frac{\overrightarrow{a}.\overrightarrow{b}}{\|a\|^{2}}\Leftrightarrow\overrightarrow{a}.\overrightarrow{b}\leq\frac{1}{2k}\|a\|^{2}.$
(11)
$\begin{split}&\frac{1}{2k}\geq\frac{\overrightarrow{a}.\overrightarrow{b}}{\|b\|^{2}}\Leftrightarrow
b^{2}-2k\overrightarrow{a}.\overrightarrow{b}\geq 0\Leftrightarrow
b^{2}-2k\overrightarrow{a}.\overrightarrow{b}+k^{2}a^{2}\geq
k^{2}a^{2}\Leftrightarrow\left(b-ka\right)^{2}\geq\left(k\|a\|\right)^{2}.\end{split}$
(12)

The proof is complete because for a point $a$, the set of all points $b$
containing in the feasible region defined by Equations (11) and (12) is equal
to
$H_{o}(p)\setminus\\{intB_{o}(c,r)\\}$. ∎

#### Note 1:

It can be verified that for the value of $\beta=2+\sqrt{2}$, the given
halfspace in (11) passes through the center of the given disk in (12). See
Lemma 9.4 in Appendix.

For $S=\\{x_{1},...,x_{n}\\}\subset\mathbb{R}^{2}$ and $x_{i}\in S$, let
$\hbar(x_{i})$ be the given halfspace by (11), and $B(x_{i})$ be the given
disk by (12). From Theorem 6.2, it can be deduced that we need to do

  * •

$n$ halfspace range counting approximations to approximate
$\operatorname{\textit{SkD}}_{1}(q;S)$ because

$\operatorname{\textit{SkD}}_{1}(q;S)=\frac{1}{2}\sum_{i=1}^{n}|\hbar(x_{i})|.$

  * •

$n$ halfspace and $n$ disk range counting approximations to approximate
$\operatorname{\textit{SkD}}_{\infty}(q;S)$ because

$\operatorname{\textit{SkD}}_{\infty}(q;S)=\frac{1}{2}\sum_{i=1}^{n}(|\hbar(x_{i})|-|B(x_{i})|).$

  * •

$n$ halfspace, $n$ disk, and $n$ circular cap range counting approximations to
approximate $\operatorname{\textit{SkD}}_{\beta}(q;S)$, for
$1<\beta<2+\sqrt{2}$, because

$\operatorname{\textit{SkD}}_{\beta}(q;S)=\frac{1}{2}\sum_{i=1}^{n}(|\hbar(x_{i})|-|B(x_{i})|+|\rho(x_{i})|),$

where $\rho(x_{i})$ is the circular cap obtained from $b(x_{i})$ cut by
$\hbar(x_{i})$.

  * •

$n$ halfspace and $n$ circular cap range counting approximations to
approximate $\operatorname{\textit{SkD}}_{\beta}(q;S)$, for
$2+\leavevmode\nobreak\ \sqrt{2}\leq\beta<\infty$, because

$\operatorname{\textit{SkD}}_{\beta}(q;S)=\frac{1}{2}\sum_{i=1}^{n}(|\hbar(x_{i})|-|\rho(x_{i})|).$

##  7 Experimental Results

In this section some experimental results are provided to support Section 5
and Theorem 6.1. We compute the planar halfspace depth and planar
$\beta$-skeleton depth of $q\in Q$ with respect to $S$ for different values of
$\beta$, where $Q$ with the size of $1000$ and $S$ with the size of $2500$ are
two sets of randomly generated points (double precision floating points)
within the square $\\{(x,y)|x,y\in[-10,10]\\}$. The results of our experiments
are summarized in Table 1 and its corresponding figures provided in Appendix.
The columns $2-4$ of Table 1 show that the halfspace depth can be approximated
by a quadratic function of the $\beta$-skeleton depth with a relatively small
value of
$d_{E}(\operatorname{\textit{SkD}},\operatorname{\textit{HD}})\approxeq
0.003$. In particular, $\operatorname{\textit{HD}}\approxeq
4.3(\operatorname{\textit{SkD}}_{\beta})^{2}-2.8(\operatorname{\textit{SkD}}_{\beta})+0.47$
if $\beta\to\infty$. Columns $5-7$ include the experimental results to support
Theorem 6.1.

##  8 Acknowledgment

The authors would like to thank Joseph O’Rourke and other attendees of
CCCG2017 for inspiring discussions regarding the relationships between depth
functions and posets.

## References

  * [1] Peyman Afshani and Timothy M Chan.  On approximate range counting and depth.  Discrete & Computational Geometry, 42(1):3–21, 2009.
  * [2] Greg Aloupis.  Geometric measures of data depth.  DIMACS series in discrete mathematics and theoretical computer science, 72:147, 2006.
  * [3] Boris Aronov and Sariel Har-Peled.  On approximating the depth and related problems.  SIAM Journal on Computing, 38(3):899–921, 2008.
  * [4] Boris Aronov and Micha Sharir.  Approximate halfspace range counting.  SIAM Journal on Computing, 39(7):2704–2725, 2010.
  * [5] David Bremner, Dan Chen, John Iacono, Stefan Langerman, and Pat Morin.  Output-sensitive algorithms for tukey depth and related problems.  Statistics and Computing, 18(3):259–266, 2008.
  * [6] David Bremner, Komei Fukuda, and Vera Rosta.  Primal-dual algorithms for data depth.  DIMACS series in discrete mathematics and theoretical computer science, 72:147, 2006.
  * [7] Timothy M Chan.  An optimal randomized algorithm for maximum tukey depth.  In Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, pages 430–436. Society for Industrial and Applied Mathematics, 2004.
  * [8] Dan Chen, Pat Morin, and Uli Wagner.  Absolute approximation of tukey depth: Theory and experiments.  Computational Geometry, 46(5):566–573, 2013.
  * [9] David L Donoho and Miriam Gasko.  Breakdown properties of location estimates based on halfspace depth and projected outlyingness.  The Annals of Statistics, pages 1803–1827, 1992.
  * [10] Ryan T Elmore, Thomas P Hettmansperger, and Fengjuan Xuan.  Spherical data depth and a multivariate median.  DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 72:87, 2006.
  * [11] Marco Fattore, Rosanna Grassi, and Alberto Arcagni.  Measuring structural dissimilarity between finite partial orders.  In Multi-indicator Systems and Modelling in Partial Order, pages 69–84. Springer, 2014.
  * [12] Sariel Har-Peled.  Geometric approximation algorithms.  Number 173. American Mathematical Soc., 2011.
  * [13] Sariel Har-Peled and Micha Sharir.  Relative (p, $\varepsilon$)-approximations in geometry.  Discrete & Computational Geometry, 45(3):462–496, 2011.
  * [14] Harold Hotelling.  Stability in competition.  In The Collected Economics Articles of Harold Hotelling, pages 50–63. Springer, 1990.
  * [15] David S. Johnson and Franco P Preparata.  The densest hemisphere problem.  Theoretical Computer Science, 6(1):93–107, 1978.
  * [16] David G Kirkpatrick and John D Radke.  A framework for computational morphology.  In Machine Intelligence and Pattern Recognition, volume 2, pages 217–248. Elsevier, 1985.
  * [17] Regina Y Liu.  Data depth: robust multivariate analysis, computational geometry, and applications, volume 72.  American Mathematical Soc., 2006.
  * [18] Regina Y Liu et al.  On a notion of data depth based on random simplices.  The Annals of Statistics, 18(1):405–414, 1990.
  * [19] Zhenyu Liu and Reza Modarres.  Lens data depth and median.  Journal of Nonparametric Statistics, 23(4):1063–1074, 2011.
  * [20] Hannu Oja.  Descriptive statistics for multivariate distributions.  Statistics & Probability Letters, 1(6):327–332, 1983.
  * [21] Peter J Rousseeuw and Mia Hubert.  Regression depth.  Journal of the American Statistical Association, 94(446):388–402, 1999.
  * [22] Peter J Rousseeuw and Ida Ruts.  Algorithm as 307: Bivariate location depth.  Journal of the Royal Statistical Society. Series C (Applied Statistics), 45(4):516–526, 1996.
  * [23] Peter J Rousseeuw and Anja Struyf.  Computing location depth and regression depth in higher dimensions.  Statistics and Computing, 8(3):193–203, 1998.
  * [24] Douglas S Shafer and Z Zhang.  Beginning statistics.  Phylis-Barnidge publisher, 304, 2012.
  * [25] Rasoul Shahsavarifar and David Bremner.  Computing the planar $\beta$-skeleton depth.  arXiv preprint arXiv:1803.05970, 2018.
  * [26] Hayim Shaul.  Range Searching: Emptiness, Reporting, and Approximate Counting.  University of Tel-Aviv, 2011.
  * [27] Christopher G Small.  A survey of multidimensional medians.  International Statistical Review/Revue Internationale de Statistique, pages 263–277, 1990.
  * [28] Anja J Struyf and Peter J Rousseeuw.  Halfspace depth and regression depth characterize the empirical distribution.  Journal of Multivariate Analysis, 69(1):135–153, 1999.
  * [29] John W Tukey.  Mathematics and the picturing of data.  In Proceedings of the international congress of mathematicians, volume 2, pages 523–531, 1975.
  * [30] Mengta Yang.  Depth Functions, Multidimensional Medians and Tests of Uniformity on Proximity Graphs.  PhD thesis, The George Washington University, 2014.
  * [31] Mengta Yang and Reza Modarres.  $\beta$-skeleton depth functions and medians.  Communications in Statistics-Theory and Methods, pages 1–17, 2017\.

##  9 Appendix

######  Lemma 9.1.

For posets $A,B$, $C$ in
$\mathbb{P}=\\{P_{t}=(S,\preceq_{t})|t\in\mathbb{N}\\}$, $d_{c}(A,B)\leq
d_{c}(A,C)+d_{c}(C,B),$ where

$d_{c}(A,B)=\dfrac{\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}|M^{A}_{ij}-M^{B}_{ij}|}{n^{2}-n}$

and

$M^{k}_{ij}=\begin{cases}1\;\;\;\;\;x_{i}\preceq_{k}x_{j}\\\
0\;\;\;\;\;\text{otherwise.}\end{cases}$

###### Proof.

$\displaystyle d_{c}(P_{f},P_{h})$
$\displaystyle=\dfrac{\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}|M^{f}_{ij}-M^{h}_{ij}|}{n^{2}-n}$
$\displaystyle=\dfrac{\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}|(M^{f}_{ij}-M^{g}_{ij})+(M^{g}_{ij}-M^{h}_{ij})|}{n^{2}-n}$
$\displaystyle\leq\dfrac{\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}(|M^{f}_{ij}-M^{g}_{ij}|+|M^{g}_{ij}-M^{h}_{ij}|)}{n^{2}-n}$
$\displaystyle=\dfrac{\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}|M^{f}_{ij}-M^{g}_{ij}|}{n^{2}-n}+\dfrac{\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}|M^{g}_{ij}-M^{h}_{ij}|}{n^{2}-n}$
$\displaystyle=d_{c}(P_{f},P_{g})+d_{c}(P_{g},P_{h}).$

∎

######  Lemma 9.2.

For $\beta^{\prime}>\beta\geq 1$ and $a,b\in\mathbb{R}^{2}$,
$S_{\beta}(a,b)\subseteq S_{\beta^{\prime}}(a,b)$, where $S_{\beta}(a,b)$ is
the intersection of two disks $B(C_{ab\beta},R_{ab\beta})$ and
$B(C_{ba\beta},R_{ba\beta})$, $C_{ab\beta}=(\beta/2)(a-b)+b$, and
$R_{ab\beta}=(\beta/2)d(a,b)$.

###### Proof.

To prove that $B(C_{ab\beta},R_{ab\beta})\cap B(C_{ba\beta},R_{ba\beta})$ is a
subset of $B(C_{ab\beta^{\prime}},R_{ab\beta^{\prime}})\cap
B(C_{ba\beta^{\prime}},R_{ba\beta^{\prime}})$, it is enough to prove
$B(C_{ab\beta},R_{ab\beta})\subseteq
B(C_{ab\beta^{\prime}},R_{ab\beta^{\prime}})$ and
$B(C_{ba\beta},R_{ba\beta})\subseteq
B(C_{ba\beta^{\prime}},R_{ba\beta^{\prime}})$. We only prove the first one,
and the second one can be proved similarly. Suppose that
$\beta<\beta^{\prime}=\beta+\varepsilon;\varepsilon>0$. It is trivial to check
that two disks $B(C_{ab\beta},R_{ab\beta})$ and
$B(C_{ab\beta^{\prime}},R_{ab\beta^{\prime}})$ meet at $b$. See Figure 6. Let
$t\neq b$ be an extreme point of $B(C_{ab\beta},R_{ab\beta})$. This means that

$\displaystyle d(t,C_{ab\beta})$ $\displaystyle=R_{ab\beta}\Leftrightarrow
d(t,\frac{\beta(a-b)}{2}+b)=\frac{\beta(d(a,b))}{2}$
$\displaystyle\Leftrightarrow\left|\frac{\beta(a-b)}{2}+(b-t)\right|^{2}=\left(\frac{\beta(a-b)}{2}\right)^{2}$
$\displaystyle\Leftrightarrow|b-t|^{2}-\beta(b-a)\cdot(b-t)=0$

This means $(b-a)\cdot(b-t)\geq 0$. Hence,

$\displaystyle|b-t|^{2}-\beta(b-a)\cdot(b-t)=0\Leftrightarrow$
$\displaystyle|b-t|^{2}-(\beta+\varepsilon)(b-a)\cdot(b-t)<0\Leftrightarrow$
$\displaystyle|b-t|^{2}-\beta^{\prime}(b-a)\cdot(b-t)<0\Leftrightarrow$
$\displaystyle d(t,C_{ab\beta^{\prime}})-R_{ab\beta^{\prime}}<0$

The last inequality means that $t$ is an interior point of
$B(C_{ab\beta^{\prime}},R_{ab\beta^{\prime}}).$ ∎

Figure 6: $S_{\beta}(a,b)$ and $S_{\beta^{\prime}}(a,b)$ .

######  Lemma 9.3.

For $a,b\in\mathbb{R}^{2}$,

$\lim_{\beta\to\infty}\delta=\lim_{\beta\to\infty}(h_{(\beta+1)\l}-h_{\beta\l})=0,$
(13)

where $h_{\beta\l}=(\l/2)\sqrt{(2\beta-1)}$. See Figure 6.

###### Proof.

Instead of proving (13), we prove its equivalent form as follows:

$\displaystyle\lim_{\beta\to\infty}\frac{h_{(\beta+1)\l}}{h_{\beta\l}}=\lim_{\beta\to\infty}\frac{(\l/2)\sqrt{(2\beta+1)}}{(\l/2)\sqrt{(2\beta-1)}}=\lim_{\beta\to\infty}\frac{\sqrt{(2\beta+1)}}{\sqrt{(2\beta-1)}}=1.$

∎

######  Lemma 9.4.

For $k=\beta/(2(\beta-1))$ and $a,b\in\mathbb{R}^{2}$ ($a$ is fixed and $b$ is
arbitrary), halfspace
$\overrightarrow{a}.\overrightarrow{b}\leq(1/2k)\|a\|^{2}$ passes through the
center of disk $(b-ka)^{2}\geq(k\|a\|)^{2}$ if $\beta=2+\sqrt{2}$.

###### Proof.

It is enough to substitute $b$ in the given halfspace with $ka$ which is the
center of the given disk.

$\displaystyle\overrightarrow{a}.\overrightarrow{(ka)}\leq\frac{1}{2k}\|a\|^{2}\Rightarrow
k\|a\|^{2}\leq\frac{1}{2k}\|a\|^{2}\Rightarrow 2k^{2}\leq 1\Rightarrow$
$\displaystyle 2(\frac{\beta}{2(\beta-1)})^{2}\leq
1\Rightarrow-\beta^{2}+4\beta-2\leq 0\Rightarrow\beta=2\pm\sqrt{2}$

Since $\beta\geq 1$, the $\beta=2+\sqrt{2}$ is valid. ∎

Table 1: Summary of experimental results x | $\operatorname{\textit{HD}}=f(x)$ | $d_{E}(x,\operatorname{\textit{HD}})$ | Figure | $f(x,\operatorname{\textit{SkD}}_{\infty})$ | $d_{E}(x,\operatorname{\textit{SkD}}_{\infty})$ | Figure
---|---|---|---|---|---|---
$\operatorname{\textit{SkD}}_{1}$ | $3.103x^{2}-0.013x+0.013$ | $0.0016$ | 7 | $0.942x+0.288$ | $0.007$ | 12
$\operatorname{\textit{SkD}}_{2}$ | $2.71x^{2}-0.48x+0.04$ | $0.0019$ | 8 | $0.858x+0.23$ | $0.002$ | 13
$\operatorname{\textit{SkD}}_{3}$ | $2.92x^{2}-0.82x+0.08$ | $0.0021$ | 9 | $0.86x+0.192$ | $0.001$ | 14
$\operatorname{\textit{SkD}}_{1000}$ | $4.26x^{2}-2.76x+0.47$ | $0.0031$ | 10 | $0.999x+0.002$ | $0.0$ | 15
$\operatorname{\textit{SkD}}_{10000}$ | $4.27x^{2}-2.78x+0.47$ | $0.0031$ | 11 | $1.0x+0.0$ | $0.0$ | 16

Figure 7: $\operatorname{\textit{HD}}$ verses
$\operatorname{\textit{SkD}}_{1}$. Figure 8: $\operatorname{\textit{HD}}$
verses $\operatorname{\textit{SkD}}_{2}$. Figure 9:
$\operatorname{\textit{HD}}$ verses $\operatorname{\textit{SkD}}_{3}$. Figure
10: $\operatorname{\textit{HD}}$ verses $\operatorname{\textit{SkD}}_{1000}$.
Figure 11: $\operatorname{\textit{HD}}$ verses
$\operatorname{\textit{SkD}}_{10000}$. Figure 12:
$\operatorname{\textit{SkD}}_{\infty}$ verses
$\operatorname{\textit{SkD}}_{1}$. Figure 13:
$\operatorname{\textit{SkD}}_{\infty}$ verses
$\operatorname{\textit{SkD}}_{2}$. Figure 14:
$\operatorname{\textit{SkD}}_{\infty}$ verses
$\operatorname{\textit{SkD}}_{3}$. Figure 15:
$\operatorname{\textit{SkD}}_{\infty}$ verses
$\operatorname{\textit{SkD}}_{1000}$. Figure 16:
$\operatorname{\textit{SkD}}_{\infty}$ verses
$\operatorname{\textit{SkD}}_{10000}$.