Invariance of K-medoids clustering under distance measure

Question

Suppose we have n data points $X_1,X_2,...X_n$ where $X_i \in \mathbb{R^p}$ and we are performing k-medoids clustering to this dataset. Will the iterative (PAM) algorithm with identical initialization give the same cluster results between the choice of distance measure as sum of absolute distances or $L_1$ norm vs sum of squared distances or squared $L_2$ norm?

The assignment step will be identical between the two measures as points relatively close to chosen cluster medoid in absolute distance will still be close in squared distance, but I am not very sure about the cluster medoid re-assignment step. I am trying to come up with a counterexample to demonstrate different results but unable to find anything. Would appreciate any help on this question.

If the question was for k-means instead of k-medoid, I believe the answer would be yes, the cluster results will be identical as distance measure is only used during the assignment step and any monotone transformation would preserve the ordering. Let me know if I am missing something here.

Answer 1

No, the assignment step can already differ.

Consider the means (0,0) and (5,2).

A point at (2,2) has L1 distances 4 resp. 3 and squared L2 distances 8 resp. 9. So it will be assigned to a different cluster. The nearest L1 is not the nearest L2.

Where the assignment would not make a difference is unsquared Euclidean vs. squared Euclidean. In that case, only the second step varies, 1d with a single far-out data point is enough to show this.