**The Simplical Depth Median (Liu 1988)**

Another interpretation of the univariate median is that it is the point
which lies inside the greatest
number of intervals constructed from the data points. Liu generalized this
idea as follows: Find the point
in R^{p} which is contained in the most simplexes formed by subsets of
p+1 data points (see fig.6).
This median is affine equivariant. Not much information is available about the
breakpoint.

A brute force method of finding the simplical depth median in R^{2}
is to partition the plane into cells which have segments between points as
boundaries (fig.7 has cells A-I). First, notice that every point within a
given cell has a "common destiny" (i.e. equal depth). Furthermore, a point
on a boundary between two cells must have depth at least as much as any adjacent
interior point. Similarly, an intersection point (where more than two cells
meet) must have a depth at least as much as any adjacent boundary point.
Therefore we must determine how many triangles contain each intersection point.
There are O(n^{4})
intersection points and O(n^{3}) triangles for *n* points,
so in O(n^{7}) time, we can find the simplical depth median.
Note that it is possible to find the simplical depth of a point in O(nlogn)
time, so we can achieve a straightforward algorithm in O(n^{5}logn).