I'd use the k-means algorithm clustering (with k = n) to find the n centroids and use these centroids as the set R.
k-means minimizes the expected L2 distance (i.e. $|x-c|^2$, not $|x-c|$, in case that's important -- in many cases it's not) between a point and its centroid. If all of your new testing points are in the training set, then the ideal distance (in S) would be 0, and the new distance (in R given by the centroids) will be minimized by k-means. If your testing points are different from the training points, but come from the same distribution, then this will minimize an upper bound on the distance.
In principle, k-means clustering is NP-hard in most cases. One particular algorithm (called k-means algorithm) seems to work well in many practical cases.
