Easy way to prove that this algorithm eventually terminates
Here's the solution for the case $k = 1$:

Assume the algorithm does not terminate.  Since there are a finite number of states of the algorithm (assignments of points to $A$ and $B$), the algorithm state must repeat in a cycle.  Since the cycle goes through different states, there must be a point that switches between $A$ and $B$ infinitely often.

Let $x$ be a point that switches infinitely often in this cycle.  Pick the first iteration of the algorithm within the cycle during which $x$ switches from $B$ to $A$.  For $x$ to switch to $A$, there must have been at least one point $x'$ in $A$, with $d_x^C &gt; dist(x, x')$.  Arbitrarily pick the smallest-labeled such point; define a function $f$ so that $f(x) = x'$.  Note that $x'$ also must switch between $A$ and $B$ infinitely often (because if $x'$ stayed in $A$ permanently, so would $x$), so we can take $f(f(x)), f(f(f(x))),$ etc.

Since we have a finite number of points, the iterates of f must eventually repeat:  $f^n(x) = f^m(x)$ for some $m &gt; n$.  Now look at the corresponding sequences of distances from C:  $d_{f(x)}^C, d_{f^2(x)}^C, ... d_{f^n(x)}^C, ... $.  Since it repeats, this sequence cannot be uniformly decreasing.  There must be an iterate $o$ such that $d_{f^{o-1}(x)}^C \leq d_{f^o(x)}^C$

Now, $f^{o-1}(x)$ and $f^o(x)$ are close enough to each other to cause each other to be in $A$, if one of them is.  That is, they're closer to each other than either of them is to $C$:
$d_{f^o(x)}^C \geq d_{f^{o-1}(x)}^C &gt; dist(f^{o-1}(x), f^o(x))$  (from definition of $f$)

So as soon as $f^{o-1}(x)$ and $f^o(x)$ are both in $A$, they will keep each other in $A$ forever (see lines 1-2 of the algorithm).  This contradicts the fact that all the iterates of $f$ must switch sets infinitely often.  Thus, for the case when $k = 1$, the algorithm terminates.