@vzn this was also my question. It is easier to follow than this one but harder to solve. Indeed, in this question we have a fixed set $C$ and we change $A$ and $B$ according to the distance of their elements to this fixed set $C$. While in the other question I have two sets $A$ and $B$ which changes one according to the other.

Yes it does works for $k > 1$. I didn't found manually any counter example where the algorithm can stuck inside an infinite loop. I also confirmed that experimentally (by running it for a long time on randomly generated points). It only remains for me to prove that it terminates, but I can't find which function or quantity is minimised at each iteration.

@DavidRicherby I'm not criticizing ;) I actually discussed about that solution with "causative" (who gave this answer) on IRC and we found that it will not be possible to prove it this way for $k > 1$; so we deduced that it is much better if we can derive a potential function which can be shown to be decrease at each iteration. My comment was just informative.

If you have 4 points, you cannot compute the mean distance from a given point to the 2 nearest points of each set because there is no sufficient number of points. Tale two points labelled with A and two points labelled with B: if you take one point x from A, then there is only one nearest point to x in A. K should be chosen > min(|A|,|B|). Moreover, you cannot give any example where the algorithm does not terminate even for $k > 1$. If you ave a conter example please give it (I tried but did not found).

Do this reasoning still exactly the same if we consider $d_x^S$ to be the mean distance from $x$ to its $k$ nearest points in $S$ ? That is $x$ is moved from $A$ to $B$ if the distance from $x$ to its $k$ nearest points in $A$ is higher than the distance to its $k$ nearest points in $B$. Actually, in the case that you described (and that I mentionel in my question) $k$ is $1$, and at each iteration a given point $x$ takes the label of its nearest point (linked to it by an edge), so what would this situation becomes if $k > 1$ ? Would that reasoning be the same ? Thank you.

@YuvalFilmus yes the question is why are there no cycles, how to prove that.

This is somehow complicated and may be shown only for $k = 1$. Rather, it is much better if we can derive a potential function which can be shown to be increasing or decreasing at each iteration. Or a that can be shown to be increasing or decreasing after "some" iterations rather than 1.

@RichardRast To make the explanation simple: the purpose is to better separate the sets $A$ and $B$ such that "the points of $B$ are more similar to those of a known fixed set $C$" and "the points of $A$ are finally self-similar and farther from those of $C$ and the final set $B$".