of a set or multiset $S$ will be written as $\#S$. The convex hull of a set or multiset $S\subset\mathbb{R}^n$ will be denoted by $[S]$, where $[x_1,\ldots,x_n]$ abbreviates $[\{x_1,\ldots,x_n\}]$ for finite multisets. The volume ($n$-dimensional measure) of a measurable point set $S\subset\mathbb{R}^n$ will be written as $\lvert S\rvert$. In particular, $\bigl\lvert[S]\bigr\rvert$ is the volume of the convex hull of $S$.

The concatenation of functions $g$ and $f$ will be denoted by $f\circ g$, i.e., $(f\circ g)(x) := f (g (x))$. At some points, reference will be made to distributions over $\mathbb{R}$ or $\mathbb{R}^n$; their spaces will be denoted by $\mathcal{D}'(\mathbb{R})$ or $\mathcal{D}'(\mathbb{R}^n)$, respectively, compare [@Vladimirov-Book67en; @Walter-Book94].

For error estimates as well as for algorithmic complexity statements, we will use the common $\mathcal{O}$ Landau notation. Just recall that for error estimates, $\mathcal{O}(f(\varepsilon))$ denotes the set of functions $g(\varepsilon)$ which for $\varepsilon\to0$ are bounded by a constant multiple of $f(\varepsilon)$, whereas for complexity statements $\mathcal{O}(f(N))$ denotes the set of functions $g(N)$ which are bounded by constant multiples of $f(N)$ for $N\to\infty$.

Univariate Median {#sec-med}
=================

In this section, we collect basic facts about the median of real-valued data in various settings, ranging from finite multisets via countable weighted sets up to continuous 