Which potential function does this algorithm minimize or maximize?

Question

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:

1. $\forall x \in A$, if $d_x^A > d_x^B$ then move $x$ from $A$ to $B$.
2. $\forall x \in B$, if $d_x^A < d_x^B$ then move $x$ from $B$ to $A$.
3. Repeat (1) and (2) until convergence

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

Answer 1

It takes at most $|A \cup B|$ iterations until convergence. Consider the directed graph $D(V,E)$ with a vertex $v \in V$ for each point $p_v \in (A \cup B)$ and a directed edge $(u,v) \in E$ such that $p_v, v \neq u$ is the nearest point to $p_u$ (connect each point to its nearest neighbour point).

If points $p_u$ and $p_v$ are each other's nearest then $(u,v),(v,u) \in E$. On the other hand, there is no cycle consisting of more than two edges. For contradiction assume the corresponding points in such a cycle as $p_0,p_1,...,p_k,p_{0}$. Since each $p_{((i+1) \bmod k)}$ is the nearest point to $p_i$ the distances decrease as we go along the cycle. This means that $p_k$ is closer to $p_0$ than $p_1$ and by construction this is not possible. A cycle of length three or more could cause an infinite chain of label changes (switching between labels $A$ and $B$).

The out degree of vertices in $D$ is exactly one, and in any path the last vertex have an out edge to its previous vertex in that path (because they are mutually each other's nearest). So the last vertex change label at most once, in the first iteration. Then its label propagates backward along all the path ending at this vertex until all the vertices in those paths receive this label.

Therefore, at each iteration, at least one vertex in any path gets its final label. So the number of iterations is the length of the longest path in $D$ which is at most $|V|-1$.