Computing the Planar $β$-skeleton Depth Article Swipe
YOU?
·
· 2018
· Open Access
·
· DOI: https://doi.org/10.48550/arxiv.1803.05970
· OA: W4394649000
For $β\geq 1$, the \emph{$β$-skeleton depth} ($\SkD_β$) 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{$β$-skeleton influence region} of a random pair of points from $F$. The $β$-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 $β$-skeleton depth is based on counting all of the $β$-skeleton influence regions, obtained from pairs of points in $S$, that contain $q$. The $β$-skeleton depth introduces a family of depth functions that contains \emph{spherical depth} and \emph{lens depth} for $β=1$ and $β=2$, respectively. The straightforward algorithm for computing the $β$-skeleton depth in dimension $d$ takes $O(dn^2)$. This complexity of computation is a significant advantage of using the $β$-skeleton depth in multivariate data analysis because unlike most other data depths, the time complexity of the $β$-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 $Θ(n\log n)$ for computing the planar spherical depth, and the second algorithm with the time complexity of $O(n^{\frac{3}{2}+ε})$ is for computing the planar $β$-skeleton depth, $β>1$. By reducing the problem of \textit{Element Uniqueness}, we prove that computing the $β$-skeleton depth requires $Ω(n \log n)$ time. Some geometric properties of $β$-skeleton depth are also investigated in this paper. These properties indicate that \emph{simplicial depth} ($\SD$) is linearly bounded by $β$-skeleton depth. Some experimental bounds for different depth functions are also obtained in this paper.
