  We consider the problem of approximating the majority depth (Liu and Singh,
1993) of a point q with respect to an n-point set, S, by random sampling. At
the heart of this problem is a data structures question: How can we preprocess
a set of n lines so that we can quickly test whether a randomly selected vertex
in the arrangement of these lines is above or below the median level. We
describe a Monte-Carlo data structure for this problem that can be constructed
in O(nlog n) time, can answer queries O((log n)^{4/3}) expected time, and
answers correctly with high probability.
