Point set stratification and Delaunay depth
Preprint
Abstract
In the study of depth functions it is important to decide whether we want such a function to be sensitive to multimodality or not. In this paper we analyze the Delaunay depth function, which is sensitive to multimodality and compare this depth with others, as convex depth and location depth. We study the stratification that Delaunay depth induces in the point set (layers) and in the whole plane (levels), and we develop an algorithm for computing the Delaunay depth contours, associated to a point set in the plane, with running time O(n log^2 n). The depth of a query point p with respect to a data set S in the plane is the depth of p in the union of S and p. When S and p are given in the input the Delaunay depth can be computed in O(n log n), and we prove that this value is optimal.Keywords
All Related Versions
This publication has 14 references indexed in Scilit:
- A lower bound for computing Oja depthInformation Processing Letters, 2005
- Efficient computation of location depth contours by methods of computational geometryStatistics and Computing, 2003
- General notions of statistical depth functionThe Annals of Statistics, 2000
- Asymptotic distributions of the maximal depth estimators for regression and multivariate locationThe Annals of Statistics, 1999
- Multivariate analysis by data depth: descriptive statistics, graphics and inference, (with discussion and a rejoinder by Liu and Singh)The Annals of Statistics, 1999
- Integrating robust clustering techniques in S-PLUSComputational Statistics & Data Analysis, 1997
- Planar point location using persistent search treesCommunications of the ACM, 1986
- On the convex layers of a planar setIEEE Transactions on Information Theory, 1985
- Descriptive statistics for multivariate distributionsStatistics & Probability Letters, 1983
- Optimal Search in Planar SubdivisionsSIAM Journal on Computing, 1983