There have been significant updates on computing this median in 2D. First of all, upon completing this project, I found Oja's original paper where a straightforward (brute force) O(n6) time algorithm is proposed. Niinimaa, Oja and Nyblom gave a gradient descent algorithm, which had the same time complexity. Rousseeuw and Ruts reduced the complexity of computing the sum of areas for one point, from O(n2) to O(nlogn), so they reduced the overall complexity to O(n5logn). This bound was improved to O(n3log2n) by Mike Soss, Godfried Toussaint and myself, in a tech report, and in my M.Sc. thesis I removed another log factor. A little while later, Stefan Langerman joined us to create an algorithm which computes the Oja median in O(nlog3n) time. See the conference version (4p) or the journal version (14p). Together with Erin McLeish, I proved a lower bound of Omega(nlogn) for computing the Oja depth of a query point (see this document ).