The projection median of a set of points

Given a nonempty and finite multiset of points P in Rd, the Euclidean median of P, denoted M(P), is a point in Rd that minimizes the sum of the Euclidean (ℓ2) distances from M(P) to the points of P. In two or more dimensions, the Euclidean median (otherwise known as the Weber point) is unstable; small perturbations at only a few points of P can result in an arbitrarily large relative change in the position of the Euclidean median. This instability motivates us to consider alternate notions for location functions that approximate the minimum sum of distances to the points of P while maintaining a fixed degree of stability. We introduce the projection median of a multiset of points in R2 and compare it against the rectilinear (ℓ1) median and the centre of mass, both in terms of approximation factor and stability. We show that a mobile facility located at the projection median of the positions of a set of mobile clients provides a good approximation of the mobile Euclidean median while ensuring both continuous motion and low relative velocity.