An Optimal Algorithm for Hyperplane Depth in the Plane

Abstract

Geometric Medians Given $n$ distinct values $a_1,...,a_n \in R$, the depth of a point $x\in R$, is defined as $$d(x) = \min(|\{a_i:a_i \leq x\}|,|\{a_i:a_i \geq x\}|)$$, and a median is a point of maximum depth. There are many ways to generalize this notion to $R^d$. I will discuss two of them and present some interesting results, algorithms and open questions arising from these multivariate depth measures.