@MvG Ok, you are right for that version of the algorithm. What about the case where instead of identifying $ALL x_i \in A'$ (Step 1), I immediately move $x_i$ from A to B as soon as I detect that $d^{(A,k)}_{x_i}>d^{(B,k)}_{x_i}$ (and vice versa) ? that is we do not need A' and B', we directly move a point from A to B as soon as we detect it (and from B to A as soon as we detect it). Will we have the same problem ? I just tested that on your example and it terminates.

@HugovanderSanden if steps (2) and (3) are reversed the algorithm do note terminate. For instance in p = 1 dimension with k = 1, if A = {0, 3} and B = {2, 5} then elements of A and B will swap between A and B at each iteration. This is why, it is asymmetrical, as written.

@MvG for you example, the algorithm that I provide terminates. Let the points: x1=(-2, 0), x2=(0,1), x3=(3,0), x4=(0,-1). At the first step A' = {} because distance(x1, x2) is not higher than distance(x1, x4), and distance(x2, x1) is not higher than distance(x2, x4), see step (1) of my Algorithm. So in step (2) A still the same. Similarly, in step (3) the B' = {x4} because x4 is closer to x1 than to x3, and x3 is not put in B' because distance(x3, x2) is not less than distance(x3, x4). Now at steps (5) and (6) we end up with A = {x1,x2,x4} and B={x3}. Algo stops now subce|B|=1$\leq$k

@Greg Martin, I see for question (1), I'll remove it since it is very simple, you're rihjt. However, what about the question (2), i.e., the upper bound ?

I have edited my post to be more clear.

@VaughnClimenhaga I've just edited my post to add the Latex code.