Stefan Langerman and William Steiger have an algorithm for computing this median in O(nlog3) time. They also provided a lower bound of Omega(nlogn) for computing the halfspace depth of a point. Independently, Carmen Cortes, Francisco Gomez, Mike Soss, Godfried Toussaint and I also published this lower bound, using a different method (see the tech report or the journal version).