Abstract
This paper presents a new efficient algorithm for exactly computing the halfspace depth contours based on the idea of a circular sequence. Unlike the existing methods, the proposed algorithm segments the unit sphere directly relying on the permutations that correspond to the projections of observations onto some unit directions, without having to use the technique of parametric programming. Some data examples are also provided to illustrate the performance of the proposed algorithm.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Donoho D and Gasko M, Breakdown properties of location estimates based on halfspace depth and projected outlyingness, Ann. Statist., 1992, 20: 1808–3.
Tyler D, Finite sample breakdown points of projection based multivariate location and scatter statistics, Ann. Statist., 1994, 22: 1024–3.
Bai Z and He X, Asymptotic distributions of the maximal depth estimators for regression and multivariate location, Ann. Statist., 1999, 27: 1617–3.
Zuo Y and Serfling R, General notions of statistical depth function, Ann. Statist., 2000, 28: 461–3.
Kong L and Mizera I, Quantile tomography: Using quantiles with multivariate data, Statist. Sinica, 2012, 22: 1589–3.
Hallin M, Paindaveine D and Šiman M, Multivariate quantiles and multiple-output regression quantiles: From L 1 optimization to halfspace depth, Ann. Statist., 2010, 38: 635–3.
Paindaveine D and Šiman M, On directional multiple-output quantile regression, J. Multivariate Anal., 2011, 102: 193–3.
Tukey J, Mathematics and the picturing of data, Proceedings of the International Congress of Mathematicians, 523–531, Canada Mathematical Congress, Montreal, 1975.
Liu R, On a notion of data depth based on random simplices, Ann. Statist., 1990, 18: 191–3.
Koshevoy H and Mosler K, Zonoid trimming for multivariate distributions, Ann. Statist., 1997, 25: 1998–3.
Rousseeuw P and Hubert M, Regression depth (with discussion), J. Amer. Statist. Assoc., 1999, 94: 388–3.
Zuo Y, Projection based depth functions and associated medians, Ann. Statist., 2003, 31: 1460–3.
Mosler K, Depth statistics, Robustness and Complex Data Structures, Springer Berlin Heidelberg, 2013, 17–2.
Ghosh A and Chaudhuri P, On maximum depth and related classifiers, Scand. J. Statist., 2005, 32: 328–3.
Yeh A and Singh K, Balanced confidence regions based on Tukey’s depth and the bootstrap, J. Roy. Statist. Soc. Ser. B, 1997, 59: 639–3.
Chenouri S and Small C, A nonparametric multivariate multisample test based on data depth, Electronic J. Statist., 2012, 6: 760–3.
Rousseeuw P and Ruts I, Algorithm AS 307: Bivariate location depth, J. Roy. Statist. Soc. Ser. C, 1996, 45: 516–3.
Rousseeuw P and Struyf A, Computing location depth and regression depth in higher dimensions, Statist. Comput., 1998, 8: 193–3.
Ruts I and Rousseeuw P, Computing depth contours of bivariate point clouds, Comput. Statist. Data Anal., 1996, 23: 153–3.
Paindaveine D and Šiman M, Computing multiple-output regression quantile regions, Comput. Statist. Data Anal., 2012a, 56: 840–3.
Paindaveine D and Šiman M, Computing multiple-output regression quantile regions from projection quantiles, Comput. Statist., 2012b, 27: 29–3.
Edelsbrunner H, Algorithms in Combinatorial Geometry, Springer, Heidelberg}, 1987.
Dyckerhoff R, Computing zonoid trimmed regions of bivariate data sets, COMPSTAT 2000, Proceedings in Comput. Statist., Ed. by Bethlehem J and van der Heijden P, Physica, Heidelberg, 2000, 295–2.
Cascos I, The expected convex hull trimmed regions of a sample, Comput. Statist., 2007, 22: 557–3.
Mosler K, Lange T, and Bazovkin P, Computing zonoid trimmed regions of dimension d > 2, Comput. Statist. Data Anal., 2009, 53: 2500–3.
Floyd R and Rivest R, ‘Algorithm 489: Select’, Communications of the ACM 1975, 18: 173–3.
Barber C, Dobkin D, and Huhdanpaa H, The quickhull algorithm for convex hulls, ACM Transactions Math. Software, 1996, 22: 469–3.
Bremner D, Fukuda K, and Marzetta A, Primal-dual methods for vertex and facet enumeration, Discrete Comput. Geometry, 1998, 20: 333–3.
Rousseeuw P and Leroy A, Robust Regression and Outlier Detection, Wiley New York, 1987.
Liu X, Zuo Y, and Wang Z, Exactly computing bivariate projection depth median and contours, Comput. Statist. Data Anal., 2013, 60: 1–3.
Author information
Authors and Affiliations
Corresponding author
Additional information
This research was supported by the National Natural Science Foundation of China under Grant No. 11461029, the Natural Science Foundation of Jiangxi Province under Grant Nos. 20142BAB211014, 20132BAB211015, 20122BAB201023, 20133BCB23014, and the Youth Science Fund Project of Jiangxi provincial education department under Grant Nos. GJJ14350, GJJ14449, KJLD13033.
This paper was recommended for publication by Editor ZOU Guohua.
Rights and permissions
About this article
Cite this article
Liu, X., Ren, H. & Wang, G. Computing halfspace depth contours based on the idea of a circular sequence. J Syst Sci Complex 28, 1399–1411 (2015). https://doi.org/10.1007/s11424-015-3160-y
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11424-015-3160-y