troubleshooting Question

Closest Pair: Divide & Conquer

ProgrammingCC++
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);
}
Kashra
Learn from the best

Network and collaborate with thousands of CTOs, CISOs, and IT Pros rooting for you and your success.

Andrew Hancock - VMware vExpert
See if this solution works for you by signing up for a 7 day free trial.