The projection median of a set of points in \({\mathbb{R}}^{d}\) (Q664356): Difference between revisions

To generalize the notion of median of a set of real numbers to \({\mathbb R}^d\) a real function on \({\mathbb R}^d\) is needed. According to the function used different generalization appear. For example, if the orthogonal projections are used, then it is possible to define a vector-of-medians, also called the rectilinear median. Another possibility is to define it as the point which minimizes distances. Thus, the Euclidean median of a set is defined as the point in \({\mathbb R}^d\) which minimizes the sum of the Euclidean distances to all the points of the set. Some authors have used measures to compare different median functions: for example, the stability under perturbations of the set for which the median is computed or the notion of breakdown point (the proportion of points which must be moved to infinity so that the median function will do the same). The projection median of a set \(S\subset {\mathbb R}^d\) was introduced by \textit{S. Durocher} and \textit{D. Kirkpatrick} [Comput. Geom. 42, No. 5, 364--375 (2009; Zbl 1170.65013)] as \[ {\mathcal M} (S) = d\;\frac{\int_{S^{d-1}}\text{med}(S_u) \text{d}u}{\int_{S^{d-1}}\text{d}u}, \] where \(S^{d-1}\) is the unit \(d\)-dimensional sphere and med\((S_u)\) is the median of the projection of \(S\) onto the line through the origin parallel to vector \(u\). It is shown in the cited paper that the projection median in \({\mathbb R}^2\) maintains a fixed degree of stability (is \((\pi/4)\)-stable) while providing a better approximation of the two-dimensional Euclidean median (it is a \(4/\pi\)-approximation) than the center of mass or the rectilinear median. In the paper under review the authors study these kind of properties for the projection median in \({\mathbb R}^d\). The degree of approximation of the projection median to the \(d\)-dimensional Euclidean median is fixed. For the special case \(d=3\) the results imply that the three-dimensional projection median is a \((3/2)\)-approximation of the three- dimensional Euclidean median, which settles a conjecture posed by Durocher in his Ph. D. Thesis. Moreover, the stability bound for the \(d\)-dimensional projection median is obtained and it is shown that the breakdown point is \(1/2\).