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 **R**^{2}
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.