I have to vectors $X_1$ and $X_2$ with 3 dimensional points $p_i$ and $p_j$ contained. As long as $X_1$ is not empty, I want to find the closest pair $p_i$ and $p_j$. The point $p_i$ of this pair I need to remove from $X_1$ and add to $X_2$. To make the following analysis easier, both $X_1$ and $X_2$ contain $n$ points. The lower border for the closest pair problem is $O(n(log(n)))$.
To get the closest pair I utilize at the moment a search structure (Octree, as I am only interested in expected/average run-time). With the Octree containing the complete $X_2$ vector, I can find the closest neighbor for each Point in $X_1$ in $O(log(n))$. So I iterate through $X_1$ $n$ times, leading to $O(n(log(n)))$ for 1 closest pair. I can remove the point from $X_1$ and add to the Octree without effecting the run-time. But I have to do this $n$ times (until $X_1$ is empty), leading to $O(n^2(log(n)))$ in total.
I am interested in:
a) Any solution which is not perfect but better than this, if no answer to (b) can be given.
b) The theoretical lower complexity border of this problem, preferably with the solution.
Any ideas?
Jan