Expected runtime complexity of repeated closest Point Pair search

Question

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

Answer 1

I could reduce the problem to $O(n^2)$ runtime in the following manner:

Build a search structure (KDTree or Octree, the KDTree garanties $O(n(log(n))$ here) with $X_2$ points contained.

For each $p_i$ in $X_1$ find its closest point $p_j$. Build a List $L$ containing the pairs $p_i$,$p_j$ in addition with distance $d_{i,j}$ as a triplet. Noting the distance is only needed to avoid later computations which would not effect the runtime complexity. The whole procedure is done in $O(n(log(n))$.

Then do:

$while \ X_1 \ not empty$

$ \ \ \ \ \ \ \ \ iterate \ through \ L \ to \ find \ the \ triplet \ with \ the \ minimal \ distance$ linear time

$ \ \ \ \ \ \ \ \ add \ p_i \ from \ triplet (in \ following \ named \ p_{i \ min}) \ to \ X_2$ constant time

$ \ \ \ \ \ \ \ \ remove \ p_{i \ min} \ from \ X_1 \ and \ its \ containing \ triplet \ from \ L$ - constant time

$ \ \ \ \ \ \ \ \ check \ for \ each \ triplet \ in \ L \ if \ the \ distance \ between \ the \ found \ p_i \ and \ the \ triplet \\ memeber \ p_i \ <= d_{i,j}$ linear time

$ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ if \ yes \ replace \ triplet(p_i,p_j,d_i,j) \ with \ a \ new triplet (p_i,p_{i \ min}, d_{i, i \ min})$ constant time

$end$

The while loop is exectuted n times. Inside the loop only two linear operations are done, leading to a total execution of $n(n!)$ which is of complexity $O(n^2)$. As step one (generatint the Search structure and building the list $L$ is $O(n(log(n))$, the total complexity is limited by $O(n^2)$.