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



Does this algorithm terminate in all scenarios?
Counterexample
==============


This algorithm does not terminate. Here is a counterexample, in dimension $p=2$, with $m=n=2$ points in each set, only looking at the $k=1$ nearest neighbours.


$$
A=\left\{
\begin{pmatrix}-2\\0\end{pmatrix},
\begin{pmatrix}0\\1\end{pmatrix}
\right\}
\qquad
B=\left\{
\begin{pmatrix}3\\0\end{pmatrix},
\begin{pmatrix}0\\-1\end{pmatrix}
\right\}
$$


The two points with $0$ in their first coordinate will change sets in every iteration. After two iterations you are back where you started, so this cannot terminate.


Step by step
============


Since you doubt my counterexample in a comment below, here is a detailed step-by-step execution of your algo in this case. I'm using the same names for the points as you did:


$$
x\_1=\begin{pmatrix}-2\\0\end{pmatrix} \qquad
x\_2=\begin{pmatrix}0\\1\end{pmatrix} \qquad
x\_3=\begin{pmatrix}3\\0\end{pmatrix} \qquad
x\_4=\begin{pmatrix}0\\-1\end{pmatrix} \\
A=\{x\_1,x\_2\} \qquad B=\{x\_3,x\_4\}
$$


* $A'=\{x\_2\}$ since $d\_{x\_2}^{(A,1)}=\lVert x\_1-x\_2\rVert=\sqrt5>2=\lVert x\_4-x\_2\rVert=d\_{x\_2}^{(B,1)}$
* $A=A\setminus A'=\{x\_1\}$
* $B'=\{x\_4\}$ since $d\_{x\_4}^{(A,1)}=\lVert x\_1-x\_4\rVert=\sqrt5<\sqrt{10}=\lVert x\_3-x\_4\rVert=d\_{x\_4}^{(B,1)}$
* $B=B\setminus B'=\{x\_3\}$
* $A=A\cup B'=\{x\_1,x\_4\}$
* $B=B\cup A'=\{x\_2,x\_3\}$
* $A'=\{x\_4\}$ since $d\_{x\_4}^{(A,1)}=\lVert x\_1-x\_4\rVert=\sqrt5>2=\lVert x\_2-x\_4\rVert=d\_{x\_4}^{(B,1)}$
* $A=A\setminus A'=\{x\_1\}$
* $B'=\{x\_2\}$ since $d\_{x\_2}^{(A,1)}=\lVert x\_1-x\_2\rVert=\sqrt5<\sqrt{10}=\lVert x\_3-x\_2\rVert=d\_{x\_2}^{(B,1)}$
* $B=B\setminus B'=\{x\_3\}$
* $A=A\cup B'=\{x\_1,x\_2\}$
* $B=B\cup A'=\{x\_3,x\_4\}$


