Greedy Permutations

Let \(M\) be a finite metric space, i.e., a finite set of points with a metric \(M\times M\to R\). Let the points of \(M\) be ordered \(p_1,\ldots, p_n\). Let \(P_i:= \{p_1,\ldots, p_i\}\). This ordering is greedy if for all \(i = 2\ldots n\), we have

\[d(p_i, P_{i-1}) = \max_{q\in M} d(p_i, P_{i-1}).\]

The greedy permutation is not unique. Given any choice of the first point, it is always possible to complete the ordering to be greedy. It also implies an algorithm. At step \(i\), set \(p_i\) to be the farthest point to \(P_{i-1}\) among all the remaining points. This is not very efficient. It would take \((n-i+1)(i-1)\) distance computations to determine the \(i\) th point.