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(n^{6}) 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(n^{2}) to
O(n*log*n), so they reduced the overall complexity to
O(n^{5}*log*n).
This bound was improved to O(n^{3}*log*^{2}n) 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(n*log*^{3}n)
time. See the
conference
version (4p) or the
journal
version (14p).
Together with Erin McLeish, I proved a lower bound of Omega(n*log*n)
for computing the Oja depth of a query point (see this
document ).
Greg