I have a set *S* of real numbers, and I would like to create a new set *R* with exactly n real numbers (not necessarily from the set) that represent it best.


What I mean by best?


Well, I have query that asks for given point what is the closest point from S to that point, and when I ask same thing for set R I would like to have best fit to the real answers.



> 
> To be specific, how do I minimize the [Hausdoff distance](http://en.wikipedia.org/wiki/Hausdorff_distance) between *S* and *R*?
> 
> 
> 


I hope I've been clear enough in what i want. 
I've heard of mathoverflow, so I said to myself why wouldn't I ask for help there. 


Thank you in advance.


(**Edited** in light of the comments below.)



Approximating a set with fixed number of elements
This is the $k$-center problem (or in your notation, the $n$-center problem). you're given a set $S$ of points, and you want to find a set $R$ of $n$ points such that the set of balls of radius $r$ around each point in $R$ cover all of $S$, and $r$ is minimized. 


Your metric space is the line, so this problem is relatively easy to solve. Here's a two-step approach: First, "guess" the optimal solution r (ie. pick some value of r). Now go from left to right, assigning centers greedily, which is to say, as far away from the previously placed center as possible, while covering all points. If you use up $n$ points before covering all of $S$, your guess was wrong, and you need to restart with a larger value of r. Else, you're done.


Now of course $r$ is a real number, but there are only discretely many "guesses", since the optimal r must be such that there are two points at distance exactly $r$ from a center (otherwise r is not optimal). so the total set of choices of r is merely the set constructed from measuring the pairwise distances and halving them. 


All of this assumes you're in algorithms-land, which means that you have reasonable ways of representing points and comparing them. 


p.s this algorithm is well known (not original). 


