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).
Greg