Considering two sets $A, B$ containing some $p$-dimensional points $x \in \mathbb{R}^p$. Let $d_x^S = \min_{x' \in S \setminus \{x\}} \lVert \mathbf{x} - \mathbf{x'} \rVert$ denote the Euclidean distance from $x$ to its nearest point in $S$. We have a very simple algorithm:$\forall x \in A$, if $d_x^A > d_x^B$ then move $x$ from $A$ to$B$.$\forall x \in B$, if $d_x^A < d_x^B$ then move $x$ from $B$ to$A$.Repeat (1) and (2) until convergenceConvergence is when there is no more $x \in A$ such that $d_x^A > d_x^B$, and there is no more $x \in B$ such that $d_x^A < d_x^B$.How could I figure out which function does this algorithm minimize or maximize at each iteration ? The function $\Phi(A)+\Phi(B) = \sum_{x \in A} d_x^A + \sum_{x \in B} d_x^B$ does not seem to decrease at each iteration.Note: another version of this algorithm is when we define $d_x^S$ as the mean distance from $x$ to its $k$ nearest points in $S$, instead of the distance to its nearest point in $S$. I don't know if $k > 1$ would make the proof more complicated or not.
Which potential function does this algorithm minimize or maximize?
algorithms;complexity theory;algorithm analysis;optimization