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 > d_{x_i}^C \}$ ... (1)

• $A = A \setminus A'$; $B = B \cup A'$ ... (2)

• $B' = \{ x_i \in B \mid d_{x_i}^A

• $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 incr

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 > 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 > 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 > 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.

StackExchange Computer Science Q#18393, answer score: 2