The Projection Median of a Set of Points in Rd⋆

The projection median of a finite set of points in R2 was introduced by Durocher and Kirkpatrick [Computational Geometry: Theory and Applications, Vol. 42 (5), 364–375, 2009]. They proved that the projection median in R2 provides a better approximation of the 2-dimensional Euclidean median, than the center of mass or the rectilinear median, while maintaining a fixed degree of stability. In this paper we study the projection median of a set of points in Rd for d ≥ 2. Using results from the theory of integration over topological groups, we show that the d-dimensional projection median provides a (d /π)B(d/2, 1/2)-approximation to the d-dimensional Euclidean median, where B(α, β) denotes the Beta function. We also show that the stability of the d-dimensional projection median is at least 1⁄(d/π)B(d/2,1/2), and its breakdown point is 1/2. Based on the stability bound and the breakdown point, we compare the d-dimensional projection median with the rectilinear median and the center of mass, as a candidate for approximating the d-dimensional Euclidean median. For the special case of d = 3, our results imply that the 3-dimensional projection median is a (3/2)-approximation of the 3-dimensional Euclidean median, which settles a conjecture posed by Durocher.