troubleshooting Question

Closest Pair: Divide & Conquer

Avatar of krusho
krushoFlag for United States of America asked on
ProgrammingCC++
15 Comments4 Solutions5347 ViewsLast Modified:
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);
}
ASKER CERTIFIED SOLUTION
Kashra

Our community of experts have been thoroughly vetted for their expertise and industry experience.

Join our community to see this answer!
Unlock 4 Answers and 15 Comments.
Start Free Trial
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.
Unlock 4 Answers and 15 Comments.
Try for 7 days

”The time we save is the biggest benefit of E-E to our team. What could take multiple guys 2 hours or more each to find is accessed in around 15 minutes on Experts Exchange.

-Mike Kapnisakis, Warner Bros