The projection median of a set of points (Q1025289)

Let \(P\) be a multiset of points in the plane. The point for which the function \(x\mapsto\sum_{p\in P}|x-p|\) takes its minimum value is called the \textit{Euclidean median}; it is known to be unstable in the sense that the Euclidean median of a small perturbation of \(P\) may be located at a large distance away from that of \(P\) itself. The authors define the \textit{projection median} to be the average over all one-dimensional medians obtained by orthogonally projecting \(P\) onto a line passing through the origin. They show that the projection median is stable and gives an approximation to the Euclidean median. The projection median is also compared with two common stable approximation schemes, the \textit{center of mass} and the \textit{rectilinear median.} The article is accessible to a general audience, although familiarity with computational geometry is useful.