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).
No comments:
Post a Comment