Definition - center of the cluster with non-Euclidean distance I have cluster consisting of two points and I am working with non-Euclidean distance. I wonder if it is appropriate to talk about center of cluster in this case and how we can interpret it? We can start with simpler case when distance is weighted Euclidean.

Update: Here is clarification. Assume we are using Manhattan distance to find centroid of our 2 point cluster. As far as I understand centroid is not unique in this case if we use PAM algorithm. We need to work with whole set of centroids  for one cluster. Hence, clustering might produce random results on each iteration. It looks to me that problem is not well posed.
The easiest solution for a non-Euclidean cluster center is the medoid, as in the algorithm PAM. This works with arbitrary metrics, but unfortunately for a 2-element cluster the result by definition is random (by metric properties, each point is an equally good medoid).

Or you step back and rethink what the center is. It is the point which has the least squared error. So "all" you need to do is solve some math for your distance function, how to optimize this least-squares estimation. People have been solving such problems since Gauss. For example with the deviation abs(x-mu) the least-squares objective is minimized by the arithmetic mean, an the one dimensional result carries over to the n-dimensional case and thus Euclidean distance!

Obviously, this needs to be done for every distance function again.

So if you want to interpolate a center for an other distance function, solve that optimization problem (efficiently, but try to find an existing solution first, of course).