Dan Chen
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 talk, and it is the first algorithm to compute the majority depth. This algorithm runs in O((n+m)log n) time with Brodal and Jacob's data structure, where n is the size of the point set, and m is the size of the median level in the dual arrangement of the point set. In the word RAM model, it runs in O((n+m)log n/log log n) time.