AS 307

Algorithm AS 307: Bivariate location depth. he half-space depth of a point θ relative to a bivariate data set {x 1 ,⋯,x n } is given by the smallest number of data points contained in a closed half-plane of which the boundary line passes through θ. A straightforward algorithm for the half-space depth needs O(n 2 ) steps. The simplicial depth of θ relative to {x 1 ,⋯,x n } is given by the number of data triangles Δ(x i ,x j ,x k ) that contain θ; this appears to require O(n 3 ) steps. The algorithm proposed here computes both depths in O(nlogn) time, by combining geometric properties with certain sorting and updating mechanisms. Both types of depth can be used for data description, bivariate confidence regions, p-values, quality indices and control charts. Moreover, the algorithm can be extended to the computation of depth contours and bivariate sign test statistics.


References in zbMATH (referenced in 56 articles , 1 standard article )

Showing results 1 to 20 of 56.
Sorted by year (citations)

1 2 3 next

  1. De Loera, Jesús A.; Goaoc, Xavier; Meunier, Frédéric; Mustafa, Nabil H.: The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg (2019)
  2. Tian, Yahui; Gel, Yulia R.: Fusing data depth with complex networks: community detection with prior information (2019)
  3. Durocher, Stephane; Fraser, Robert; Leblanc, Alexandre; Morrison, Jason; Skala, Matthew: On combinatorial depth measures (2018)
  4. Gagolewski, Marek: Penalty-based aggregation of multidimensional data (2017)
  5. Hubert, Mia; Rousseeuw, Peter; Segaert, Pieter: Multivariate and functional classification using depth and distance (2017)
  6. Liu, Xiaohui: Fast implementation of the Tukey depth (2017)
  7. Dyckerhoff, Rainer; Mozharovskyi, Pavlo: Exact computation of the halfspace depth (2016)
  8. Serfling, Robert; Wang, Yunfei: On Liu’s simplicial depth and Randles’ interdirections (2016)
  9. Zasenko, Olga; Stephen, Tamon: Algorithms for colourful simplicial depth and medians in the plane (2016)
  10. Hubert, Mia; Rousseeuw, Peter J.; Segaert, Pieter: Multivariate functional outlier detection (2015)
  11. Liu, Xiaohui; Ren, Haiping; Wang, Guofu: Computing halfspace depth contours based on the idea of a circular sequence (2015)
  12. Xiaohui Liu; Yijun Zuo: CompPD: A MATLAB Package for Computing Projection Depth (2015) not zbMATH
  13. Li, Zhonghua; Dai, Yi; Wang, Zhaojun: Multivariate change point control chart based on data depth for phase I analysis (2014)
  14. López-Pintado, Sara; Sun, Ying; Lin, Juan K.; Genton, Marc G.: Simplicial band depth for multivariate functional data (2014)
  15. Mustafa, Nabil H.; Tiwary, Hans Raj; Werner, Daniel: A proof of the Oja depth conjecture in the plane (2014)
  16. Chenouri, Shojaeddin; Small, Christopher G.: A nonparametric multivariate multisample test based on data depth (2012)
  17. Dutta, Subhajit; Ghosh, Anil K.: On robust classification using projection depth (2012)
  18. Elmasry, Amr: Enumerating trichromatic triangles containing the origin in linear time (2012)
  19. Elbassioni, Khaled; Elmasry, Amr; Makino, Kazuhisa: Finding simplices containing the origin in two and three dimensions (2011)
  20. Zuo, Yijun; Lai, Shaoyong: Exact computation of bivariate projection depth and the Stahel-Donoho estimator (2011)

1 2 3 next