Does this algorithm terminate in all scenarios?

Question

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

Answer 1

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\}$