MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

3 added 155 characters in body

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.

2 added 392 characters in body

I'd use the k-means algorithm (with k = n) to find the n centroids and use these centroids as the set R. There's even

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 chance this will minimize something point and its centroid. If all of your new testing points are in the training set, then the ideal distance (maybe in S) would be 0, and the discrepancy new distance (in L2 norm)R given by the centroids) will be minimized by k-means. If your testing points are different from the training points, although I'm not surebut come from the same distribution, then this will minimize an upper bound on the distance.

1

I'd use the k-means algorithm (with k = n) to find the n centroids and use these centroids as the set R. There's even a chance this will minimize something (maybe the discrepancy in L2 norm), although I'm not sure.