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)