So I want to now split the proof into an easy case and a tricky case.
To explain why the easy case is easy lets, lets observe a property that this
greedy clustering algorithm has. Now the algorithm's philosophy is that
the squeaky wheel should get the grease. That is, the separated pair of points
that are closest to each other are the ones that should get merged.
So for this reason, because it's always the closest separated pair that get
merged, if you look at the sequence of point pairs that get merged together,
that determine the spacing in each subsequent iteration, the distances
between these sort of worst separated points is only going up over time.
At the beginning of the algorithm, the closest pair of points in the entire
point set are the ones that get directly merged.
Then those are out of the picture, and now that some further away pair of
points are separated, it determines the spacing,
then they get merged. Once they've been coalesced, then there
is still some further away pair of points, which is now the smallest
separated. They get merged, and so on.
So if you look at the sequence of distances between the pairs of points
that are directly merged by the greedy algorithm, that is only going up over
time. And this sequence culminates with the
final spacing S of the greedy algorithm. At some sense, the spacing of the output
of the greedy algorithm is the distance between the point period that would get
merged if we ran the greedy algorithm one more in moderation but unfortunately
we're not allowed to do that. Okay?
So the point is, for every pair of points directly merged by the greedy algorithm,
they're always a distance at most S away from each other.
So the easy case, then, is when this pair of points, pq,
which, on the one hand, lie in a common greedy structure,
but on the other hand, in different clusters with c hats.
If they were, at some point, not merely in the same cluster, but actually
directly merged by the greedy algorithm. If, at some iteration, they determined
the spacing, and were picked by the greedy algorithm to have their, clusters
merged. Then we just argued that the distance
between p and q is no more than the space in capital s of the greedy clustering.
And since p and q lie in different clusters of the c hats.
It's separated by the C hats and therefore they upper bound the spacing of
the C hats. Maybe there's some even closer separated
pair by the C hats. But the very least P and Q are separated
so they upper bound the spacing of the C hat clustering.
So that's what we wanted to prove. We wanted to show that this alternative
spacing didn't have better spacing than our greedy spacing.
It had to be at most as big. It had to be at most capital S.
So in this easy case, when P and Q are directly merged by the greedy algorithm,
we're done. So the tricky case is when P and Q are
only indirectly merged, and you may be wondering at the moment, what does that
mean? How did two people wind up in the same
cluster if they weren't, at some point, directly merged?
So let's draw a picture and see how that can happen.