Computing the Planar $\beta$-skeleton Depth Article Swipe
YOU?
·
· 2018
· Open Access
·
· DOI: https://doi.org/10.48550/arxiv.1803.05970
· OA: W2791122861
For $\\beta \\geq 1$, the \\emph{$\\beta$-skeleton depth} ($\\SkD_\\beta$) of a\nquery point $q\\in \\mathbb{R}^d$ with respect to a distribution function $F$ on\n$\\mathbb{R}^d$ is defined as the probability that $q$ is contained within the\n\\emph{$\\beta$-skeleton influence region} of a random pair of points from $F$.\nThe $\\beta$-skeleton depth of $q\\in \\mathbb{R}^d$ can also be defined with\nrespect to a given data set $S\\subseteq \\mathbb{R}^d$. In this case, computing\nthe $\\beta$-skeleton depth is based on counting all of the $\\beta$-skeleton\ninfluence regions, obtained from pairs of points in $S$, that contain $q$. The\n$\\beta$-skeleton depth introduces a family of depth functions that contains\n\\emph{spherical depth} and \\emph{lens depth} for $\\beta=1$ and $\\beta=2$,\nrespectively. The straightforward algorithm for computing the $\\beta$-skeleton\ndepth in dimension $d$ takes $O(dn^2)$. This complexity of computation is a\nsignificant advantage of using the $\\beta$-skeleton depth in multivariate data\nanalysis because unlike most other data depths, the time complexity of the\n$\\beta$-skeleton depth grows linearly rather than exponentially in the\ndimension $d$. The main results of this paper include two algorithms. The first\none is an optimal algorithm that takes $\\Theta(n\\log n)$ for computing the\nplanar spherical depth, and the second algorithm with the time complexity of\n$O(n^{\\frac{3}{2}+\\epsilon})$ is for computing the planar $\\beta$-skeleton\ndepth, $\\beta >1$. By reducing the problem of \\textit{Element Uniqueness}, we\nprove that computing the $\\beta$-skeleton depth requires $\\Omega(n \\log n)$\ntime. Some geometric properties of $\\beta$-skeleton depth are also investigated\nin this paper. These properties indicate that \\emph{simplicial depth} ($\\SD$)\nis linearly bounded by $\\beta$-skeleton depth. Some experimental bounds for\ndifferent depth functions are also obtained in this paper.\n
