  For $\beta \geq 1$, the \emph{$\beta$-skeleton depth} ($\SkD_\beta$) of a
query point $q\in \mathbb{R}^d$ with respect to a distribution function $F$ on
$\mathbb{R}^d$ is defined as the probability that $q$ is contained within the
\emph{$\beta$-skeleton influence region} of a random pair of points from $F$.
The $\beta$-skeleton depth of $q\in \mathbb{R}^d$ can also be defined with
respect to a given data set $S\subseteq \mathbb{R}^d$. In this case, computing
the $\beta$-skeleton depth is based on counting all of the $\beta$-skeleton
influence regions, obtained from pairs of points in $S$, that contain $q$. The
$\beta$-skeleton depth introduces a family of depth functions that contains
\emph{spherical depth} and \emph{lens depth} for $\beta=1$ and $\beta=2$,
respectively. The straightforward algorithm for computing the $\beta$-skeleton
depth in dimension $d$ takes $O(dn^2)$. This complexity of computation is a
significant advantage of using the $\beta$-skeleton depth in multivariate data
analysis because unlike most other data depths, the time complexity of the
$\beta$-skeleton depth grows linearly rather than exponentially in the
dimension $d$. The main results of this paper include two algorithms. The first
one is an optimal algorithm that takes $\Theta(n\log n)$ for computing the
planar spherical depth, and the second algorithm with the time complexity of
$O(n^{\frac{3}{2}+\epsilon})$ is for computing the planar $\beta$-skeleton
depth, $\beta >1$. By reducing the problem of \textit{Element Uniqueness}, we
prove that computing the $\beta$-skeleton depth requires $\Omega(n \log n)$
time. Some geometric properties of $\beta$-skeleton depth are also investigated
in this paper. These properties indicate that \emph{simplicial depth} ($\SD$)
is linearly bounded by $\beta$-skeleton depth. Some experimental bounds for
different depth functions are also obtained in this paper.
