The projection median of a set of points in ℝ^d

Abstract

The projection median of a finite set of points in ℝ² was introduced by Durocher and Kirkpatrick [Computational Geometry: Theory and Applications, Vol. 42 (5), 364–375, 2009]. They proved that the projection median in ℝ² provides a better approximation of the two-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 ℝ^d for d≥2. Using results from geometric measure theory 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 three-dimensional projection median is a (3/2)-approximation of the three-dimensional Euclidean median, which settles a conjecture posed by Durocher.