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 ).
Greg