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 in O((log n)4/3) expected time, and answers correctly with high probability.

Additional Metadata
Keywords Data depth, Majority depth, Median level, Range counting
Persistent URL dx.doi.org/10.1016/j.comgeo.2013.11.005
Journal Computational Geometry
Chen, D. (Dan), & Morin, P. (2015). Reprint of: Approximating majority depth. Computational Geometry, 49, 2–7. doi:10.1016/j.comgeo.2013.11.005