×

On combinatorial depth measures. (English) Zbl 1430.62282

Summary: Given a set \(P = \{p_1, \dots, p_n \}\) of points and a point \(q\) in the plane, we define a function \(\psi(q)\) that provides a combinatorial characterization of the multiset of values \(\{\vert P \cap H_i \vert \}\), where for each \(i \in \{1, \dots, n \}\), \(H_i\) is the open half-plane determined by \(q\) and \(p_i\). We introduce two new natural measures of depth, perihedral depth and eutomic depth, and we show how to express these and the well-known simplicial and Tukey depths concisely in terms of \(\psi(q)\). The perihedral and eutomic depths of \(q\) with respect to \(P\) correspond respectively to the number of subsets of \(P\) whose convex hull contains \(q\), and the number of combinatorially distinct bisections of \(P\) determined by a line through \(q\). We present algorithms to compute the depth of an arbitrary query point in \(O(n \log n)\) time and medians (deepest points) with respect to these depth measures in \(O(n^4)\) and \(O(n^{8 / 3})\) time, respectively. For comparison, these results match or slightly improve on the corresponding best-known running times for simplicial depth, whose definition involves similar combinatorial complexity.

MSC:

62R40 Topological data analysis
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
05C90 Applications of graph theory

Software:

AS 307
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aloupis, G., Geometric measures of data depth, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Vol. 72 (2006), pp. 147-158.
[2] Aloupis, G., Cortes, C., Gomez, F., Soss, M. and Toussaint, G., Lower bounds for computing statistical depth, Comp. Stat. Data Anal.40 (2002) 223-229. · Zbl 1098.62502
[3] Aloupis, G., Langerman, S., Soss, M. and Toussaint, G., Algorithms for bivariate medians and a Fermat-Torricelli problem for lines, Comput. Geom. Theor. Appl.26(1) (2003) 69-79. · Zbl 1039.62045
[4] Bajaj, C., The algebraic degree of geometric optimization problems, Discr. Comput. Geom.3(1) (1988) 177-191. · Zbl 0647.90087
[5] Barnett, V., The ordering of multivariate data, J. Roy. Stat. Soc. Ser. A (Gen.)139(3) (1976) 318-355.
[6] Bose, P., Maheshwari, A. and Morin, P., Fast approximations for sums of distances, clustering and the Fermat-Weber problem, Comput. Geom. Theor. Appl.24(3) (2003) 135-146. · Zbl 1016.65040
[7] Bremner, D., Chen, D., Iacono, J., Langerman, S. and Morin, P., Output-sensitive algorithms for Tukey depth and related problems, Stat. Comp.18(3) (2008) 259-266.
[8] Burr, M. A., Rafalin, E. and Souvaine, D. L., Simplicial depth: An improved definition, analysis, and efficiency for the finite sample case, Proc. Canadian Conf. Computational Geometry (CCCG) (2004), pp. 136-139.
[9] Chakraborty, B. and Chaudhuri, P., On a transformation and re-transformation technique for constructing an affine equivariant multivariate median, Proc. AMS124(8) (1996) 2539-2547. · Zbl 0856.62046
[10] Chakraborty, B. and Chaudhuri, P., On an adaptive transformation-retransformation estimate of multivariate location, J. Roy. Stat. Soc. Ser. B (Stat. Meth.)60(1) (1998) 145-157. · Zbl 0909.62056
[11] Chan, T. M., An optimal randomized algorithm for maximum Tukey depth, Proc. ACM-SIAM Symp. Discrete Algorithms (SODA) (2004), pp. 430-436. · Zbl 1317.68246
[12] Chen, D. and Morin, P., Approximating majority depth, Comput. Geom. Theor. Appl.46(9) (2013) 1059-1064. · Zbl 1273.65033
[13] Chen, D., Morin, P. and Wagner, U., Absolute approximation of Tukey depth: Theory and experiments, Comput. Geom. Theor. Appl.46(5) (2013) 566-573. · Zbl 1261.65021
[14] De Maesschalck, R., Jouan-Rimbaud, D. and Massart, D. L., The Mahalanobis distance, Chemometrics and Intelligent Laboratory Systems50(1) (2000) 1-18.
[15] Dey, T. K., Improved bounds for planar \(k\)-sets and related problems, Discr. Comput. Geom.19(3) (1998) 373-382. · Zbl 0899.68107
[16] S. Durocher, Geometric facility location under continuous motion, PhD thesis, University of British Columbia (2006).
[17] Durocher, S., Fraser, R., Leblanc, A., Morrison, J. and Skala, M., On combinatorial depth measures, Proc. Canadian Conf. Computational Geometry (CCCG) (2014), pp. 206-211. · Zbl 1430.62282
[18] Edelsbrunner, H. and Guibas, L. J., Topologically sweeping an arrangement, J. Comp. Syst. Sci.38(1) (1989) 165-194. · Zbl 0676.68013
[19] Elbassioni, K., Elmasry, A. and Makino, K., Finding simplices containing the origin in two and three dimensions, Int. J. Comput. Geom. Appl. (IJCGA)21(5) (2011) 495-506. · Zbl 1252.68327
[20] Fraiman, R., Liu, R. Y. and Meloche, J., Multivariate density estimation by probing depth, Lecture Notes-Monograph Series31 (1997) 415-430. · Zbl 0919.62050
[21] Fraiman, R. and Meloche, J., Multivariate L-estimation, Test8(2) (1999) 255-317. · Zbl 0942.62062
[22] Indyk, P., Sublinear time algorithms for metric space problems, Proc. Symp. Theory of Computing (STOC), Vol. 31 (1999), pp. 428-434. · Zbl 1346.68256
[23] Kirkpatrick, D. G., Optimal search in planar subdivisions, SIAM J. Comp.12(1) (1983) 28-35. · Zbl 0501.68034
[24] Koshevoy, G. and Mosler, K., Zonoid trimming for multivariate distributions, Ann. Stat.25(5) (1997) 1998-2017. · Zbl 0881.62059
[25] Langerman, S. and Steiger, W., Optimization in arrangements, Proc. Symp. Theoretical Aspects of Computer Science (STACS), , Vol. 2607 (Springer, 2003), pp. 50-61. · Zbl 1036.90512
[26] Liu, R., On a notion of data depth based upon random simplices, Ann. Stat.18 (1990) 405-414. · Zbl 0701.62063
[27] Liu, R. Y. and Singh, K., A quality index based on data depth and multivariate rank tests, J. ASA88(421) (1993) 252-260. · Zbl 0772.62031
[28] Liu, Z. and Modarres, R., Lens data depth and median, J. Nonparametric Stat.23(4) (2011) 1063-1074. · Zbl 1230.62075
[29] Mosler, K. and Hobert, R., Data analysis and classification with the zonoid depth, DIMACS Ser. Discr. Math. Theor. Comp. Sci.72 (2006) 49.
[30] Mustafa, N. H., Ray, S. and Shabbir, M., Ray-shooting depth: Computing statistical data depth of point sets in the plane, Proc. European Symp. Algorithms (ESA) (Springer, 2011), pp. 506-517. · Zbl 1347.68342
[31] Oja, H., Descriptive statistics for multivariate distributions, Stat. Prob. Lett.1 (1983) 327-332. · Zbl 0517.62051
[32] Rousseeuw, P. J., Multivariate estimation with high breakdown point, Math. Stat. Appl.8 (1985) 283-297. · Zbl 0609.62054
[33] Rousseeuw, P. J. and Ruts, I., Bivariate location depth, J. Roy. Stat. Soc. Ser. C (Appl. Stat.)45(4) (1996) 516-526. · Zbl 0905.62002
[34] M. I. Shamos, Geometry and statistics: Problems at the interface, Technical report, DTIC Document (1976). · Zbl 0394.62002
[35] Small, C. G., A survey of multidimensional medians, Int. Stat. Rev.58(3) (1990) 263-277.
[36] Titterington, D. M., Estimation of correlation coefficients by ellipsoidal trimming, J. Roy. Stat. Soc. Ser. C (Appl. Stat.)27(3) (1978) 227-234. · Zbl 0436.62062
[37] Tukey, J., Mathematics and the picturing of data, Proc. Int. Cong. Math. (1975), pp. 523-531. · Zbl 0347.62002
[38] A. Weber, Theory of the location of industries [translated by C. J. Friedrich from Weber’s 1909 book] (1929).
[39] Zuo, Y. and Serfling, R., General notions of statistical depth function, Ann. Stat.28(2) (2000) 461-482. · Zbl 1106.62334
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.