RECORD
Computing the Planar $\beta$-skeleton Depth
Computational Geometry · Submitted 15 Mar 2018
abstract compiled · 2026-09-23 · no language-model review
The authors' main claim 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$.
The compiled record
The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
Open the compiled record
The abstract, sentence by sentence
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.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | 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$. | background 0.97 | 0.12 | 0.03 | asserted 1.00 |
| s1 | 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$. | background 0.98 | 0.14 | 0.02 | asserted 0.96 |
| s2 | 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$. | background 0.56 | 0.13 | 0.02 | asserted 1.00 |
| s3 | 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. | background 0.85 | 0.27 | 0.04 | asserted 1.00 |
| s4 | The straightforward algorithm for computing the $\beta$-skeleton depth in dimension $d$ takes $O(dn^2)$. | background 0.80 | 0.40 | 0.05 | asserted 1.00 |
| s5 | 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$. | interpretation 0.90 | 0.29 | 0.07 | asserted 1.00 |
| s6 | The main results of this paper include two algorithms. | contribution 0.95 | 0.89 | 0.18 | asserted 0.99 |
| s7 | 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$. | contribution 0.79 | 0.95 | 0.58 | asserted 1.00 |
| s8 | By reducing the problem of \textit{Element Uniqueness}, we prove that computing the $\beta$-skeleton depth requires $\Omega(n \log n)$ time. | result 0.88 | 0.92 | 0.14 | asserted 1.00 |
| s9 | Some geometric properties of $\beta$-skeleton depth are also investigated in this paper. | contribution 0.97 | 0.89 | 0.03 | asserted 0.89 |
| s10 | These properties indicate that \emph{simplicial depth} ($\SD$) is linearly bounded by $\beta$-skeleton depth. | result 0.96 | 0.84 | 0.06 | hedged possibility 0.79 |
| s11 | Some experimental bounds for different depth functions are also obtained in this paper. | result 0.75 | 0.93 | 0.03 | asserted 0.98 |
What was examined, and what was not
- arXiv listing abstract v1
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
The paper
Original abstract
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.
Human review
How the literature uses it
2 arXiv papers cite this in 2 sentences
Papers citing it · 1 sentence without a confident label
Cites it as background 1 paper
-
Some recent comparative simulation study in $ℝ^k$ might be found in [ref] .
Connecting pairwise spheres by depth: DCOPS · Concluding remarks · 0.80
Discussion
Know something about this paper? Leave a comment, or highlight any passage above to comment on it.