Let $x \in \mathbb{R}^p$ denote a $p$-dimensional data point (a vector). I have two sets $A = \{x_1, \dots, x_n\}$ and $B = \{x_{n+1}, \dots, x_{n+m}\}$, so $|A| = n$, and $|B| = m$. Given $k \in \mathbb{N^*}$, let $d_x^{(A, k)}$ denote the mean Euclidean distance from $x$ to its $k$ nearest points in $A$; and $d_x^{(B, k)}$ denote the mean Euclidean distance from $x$ to its $k$ nearest points in $B$.

I have the following algorithm:

• $A' = \{ x_i \in A \mid d_{x_i}^{A, k)} > d_{x_i}^{(B, k)} \}$ ... (1)
• $A = A \setminus A'$ ... (2)
• $B' = \{ x_i \in B \mid d_{x_i}^{A, k)} < d_{x_i}^{(B, k)}$ ... (3)
• $B = B \setminus B'$ ... (4)
• $A = A \cup B'$ ... (5)
• $B = B \cup A'$ ... (6)
• Repeat (1), (2), (3), (4), (5) and (6) 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)

Does this algorithm terminate, and if so, is it possible to easily prove it ? Is it also possible to have an upper bound for the number of iterations required to terminate ?

Note: "The $k$ nearest points to $x$ in a set $S$" means: The $k$ points (other than $x$) in $S$, having the smallest Euclidean distance to $x$.