Stefan Langerman, Mike Soss, Godfried Toussaint and myself have an
O(n4) time algorithm for computing this median in 2D.
See the
tech report ,
conference version
, or
journal version
.
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)
Greg