Easy way to prove that this algorithm eventually terminates Introduction and notations:

Here is a new and simple version of my algorithm which seems to terminates (according to my experiments), and now I would like to prove that.

Let the notation $x_i \in \mathbb{R}^p$ refer to a $p$ dimensional data point (a vector). I have three sets A, B and C, such that $|A| = n$, $|B| = m$, $|C| = l$:
$$A = \{x_i | i = 1, .., n\}$$
$$B = \{x_j | j = n+1, .., n+m\}$$
$$C = \{x_u | u = n+m+1, .., n+m+l\}$$

Given $k \in \mathbb{N^*}$, let $d_{x_i}^A$ denote the mean Euclidean distance from $x_i$ to its $k$ nearest points in $A$; and $d_{x_i}^C$ denote the mean Euclidean distance from $x_i$ to its $k$ nearest points in $C$.

Algorithm:

I have the following algorithm which iteratively modifies the sets A and B by moving some selected elements from A to B and vis versa, and C remains always the same (do not change). To make it simple: the purpose of the algorithm 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$":


$A' = \{ x_i \in A \mid d_{x_i}^A &gt; d_{x_i}^C \}$ ... (1)
$A = A \setminus A'$; $B = B \cup A'$ ... (2)
$B' = \{ x_i \in B \mid d_{x_i}^A &lt; d_{x_i}^C$ } ... (3)
$B = B \setminus B'$; $A = A \cup B'$ ... (4)
Repeat (1), (2), (3), and (4) until: (no element moves from $A$ to $B$ or from $B$ to $A$, that is A' and B' become empty) or ($|A| \leq k$ or $|B| \leq k$)


The algorithm terminates in two cases:


when $|A|$ or $|B|$ becomes less than or equals to $k$
or the most standard case, when $A' = B' = \emptyset$, which means that no more elements moves between A and B.


Question:

How to prove that this algorithm eventually terminates ? I didn't found a convenient potential function which can be strictly minimized or maximized by the algorithm.
I have unsuccessfully tried some functions: the function $\sum_{x \in A} d_x^C + \sum_{x \in B} d_x^A$ but it is not increasing at each iteration. The function $\sum_{x \in A} d_x^A + \sum_{x \in B} d_x^C$ but it is not decreasing at each iteration. The function $\sum_{x \in A} d_x^A + \sum_{x \in B} d_x^B$ seems not to be decreasing at each iteration. The function $\sum_{x \in A} d_x^B + \sum_{x \in B} d_x^A$ seems not to be increasing at each iteration. So what is the convenient potential function which can be show to either increase or decrease at each iteration ? Or should we show that the function decreases but not at each iteration (after some iterations rather) ? How ?

Notes:


The $k$ nearest points to $x$ in a set $S$, means: the $k$ points
(others than $x$) in $S$, having the smallest Euclidean distance to
$x$. You can just take $k = 1$ to simplify the analysis.
I don't know if this may help or not, but I have the following
property for my initial sets $A, B, C$: initially $\forall x_i \in B,
   x_j \in A$, if $x_b \in C$ is the nearest point to $x_i$ and $x_a \in
   C$ is the nearest point to $x_j$ then always $distance(x_i, x_b) &lt;
   distance(x_j, x_a)$. This intuitively means that points in $B$ are
closer to $C$ than points in $A$.
If that makes the analysis easier: it is totally possible to consider a slightly different version of the Algorithm where as soon as a point from $A$ should be moved to $B$, it is moved from $A$ to $B$ (without passing by $A'$), and vis versa for $B$.
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.