Stefan Langerman, Mike Soss, Godfried Toussaint and myself have an
O(n4) time algorithm for computing this median in 2D.
tech report ,
A lower bound for computing the simplicial depth of one point appears
in the same paper as the lower bound for Halfspace depth (see
update of previous section)