**The Halfspace Median (Tukey 1975)**

Note: Although Tukey is credited with the notion of the halfspace median, it was Hotelling in 1929 who introduced this interpretation for the univariate median.

In order to define the halfspace median, we must first consider the notion of *depth* for a given point in R^{2}:
For each closed halfspace that contains the point, count the number of
*data* points which are not in the halfspace.
Take the minimum number found over all halfspaces to be the depth of that
point. (ex: in 2D, for a given point, place a line through it so that
the number of data on one side of the line is minimized).

The halfspace median of a data set is any point in R^{p}
which has maximum depth.

The halfspace median is generally not a unique point. However the set of points of maximal depth is guaranteed to be a closed, bounded convex set. This median is affine equivariant, and can have a breakdown point between 1/(p+1) and 1/3.

Notice that any point outside of the convex hull of the data has depth zero.
To find the region of maximum depth in R^{2}, we can use the
fact that its boundaries are segments of lines passing through pairs of data.
In other words, the vertices of the desired region must be
intersection points of lines through pairs of data. There are O(n^{4})
intersection points, and it takes O(nlogn) time to find the depth of one point,
so in O(n^{5}logn) time, we can find the intersection points of
maximum depth. We may find the convex hull of these points in O(nlogn) time,
and then compute the centroid if we do not have a unique point. Thus the
overall time complexity is O(n^{5}logn).

Note: The halfspace median may be found in
O(n^{2}log^{2}n) time with a slightly more complicated
method (Rousseeuw '98).