I'm having trouble showing that this algorithm is 2-approx.
We are given a set P of n points on the plane, and a positive integer k. We want to partition these points into k sets such that the largest distance between any two points which belong to the same part is minimized. Show that the following is a 2-factor approximation algorithm.
Set S = ∅.
For i = 1, . . . , k do
Select the farthest point from S and add it to S.
Put each point p ∈ P in the same part as the closest point in S to p.
I honestly don't know where to start. I can see that after each iteration, the distance between any point in P and the points in S become smaller. But after that I can't really see any good observations.