Closest Pair Algorithm

Question

I want to find the most optimal algorithm for finding closest ordered pairs and link them.

For example: Go thru the vector, one by one

For each one set the next according to a set of various conditions

For example, something like:

A B X C Y Z D

First we will link A to B Then when we have a look at B, we will link B to C Next when we consider X, we will link X to Y Next when we consider C, we will link C to D ... and so on

Currently someone has completed this task with some nested loops that are genuinely sub-par and it completes in O(n^2) time. Not to mention it doesn't work. What might be a better algorithm?

Here is what the current algorithm is:

for(i in list)
  while (i and j) is not linked 
     increment j
  if j is not the end
     while ++j is not the end  
       if link exists (i and j)
       break
     end while
     set link i to j
  end if
end for

I was going to write my own but I have a feeling I've seen this problem before at university and there was a simple solution to it..? Can anyone point me in the right direction please?

Answer 1

An alternative approach could be

1. Scan the vector and insert all elements into a self-balancing BST (AVL or Red-Black Tree etc etc, your pick) along with its index in the vector. $Node := (Value,VectorIndex)$

2. Then you have two choices

   • Scan the vector again, and for each element, search for it in the BST, and find its successor. Link the element and its successor in the vector.
   • Do an inorder traversal of the BST and for every pair of consecutive nodes visited in the BST, link their corresponding elements in the vector.

Either way, step 1 and 2 each take $O(n\space log \space n)$, hence the total algorithm ends up with a time complexity of $O(n \space log \space n)$ and space complexity of $O(n)$.