Algorithms for Bivariate Majority Depth.
Dan Chen, Pat Morin · 2011
The majority depth of a point with respect to a point set is the number of major sides it is in. An algorithm for majority depth in R2 is given in this paper, and it is the first algorithm to compute the majority depth. This algorithm runs in O((n+m) log n) ( time with Brodal) and log n Jacob’s data structure, and in O (n + m) log log n time in the word RAM model. 1