Solved

# Closest Pair: Divide & Conquer

Posted on 2007-07-26

Ok, what I'm trying to do is take my function which is basically closest pair, and change it from the brute force method it currently is and turn it into a divide and conquer approach. I'm having some issues understanding the descriptions of the problem I've found so far, so I was hoping to get some pseudo-code for c/c++ or possibly some code. In the end this should get the minimum distance between any 2 points in an array of 3D points. What I currently have works, but it's basically O( (N*(N+1))/2 ) and I've read with

divide and conquer it can be made into O( N*log(N) ).

I'm trying to write this in only C, so try to keep C++ stuff out for now.

typedef struct Vect // Vector struct for positions

{

float x;

float y;

float z;

} Vect_t;

float findMinDistance_old(const int nPlayers, const Vect_t *playerArray)

{ // O( (N *(N + 1)) / 2) )

Vect_t tmpVect;

float tmpDist, minDist = 0.0f;

int i, j;

if(nPlayers <= 1) return 0; // error

else if(nPlayers == 2)

{

// need this check because my loops won't work for 2 players

tmpVect.x = playerArray[0].x - playerArray[1].x;

tmpVect.y = playerArray[0].y - playerArray[1].y;

tmpVect.z = playerArray[0].z - playerArray[1].z;

tmpDist = (tmpVect.x * tmpVect.x)

+ (tmpVect.y * tmpVect.y)

+ (tmpVect.z * tmpVect.z);

return (float)sqrt(tmpDist);

}

for(i = nPlayers; --i; )

for(j = i; --j; )

{

tmpVect.x = playerArray[i].x - playerArray[j].x;

tmpVect.y = playerArray[i].y - playerArray[j].y;

tmpVect.z = playerArray[i].z - playerArray[j].z;

tmpDist = (tmpVect.x * tmpVect.x)

+ (tmpVect.y * tmpVect.y)

+ (tmpVect.z * tmpVect.z);

if(tmpDist < minDist || minDist == 0) minDist = tmpDist;

}

return (float)sqrt(minDist);

}