distance between two points, a & b = SQRT[ (xa-xb)^2 + (ya- yb)^2) ]
Define d = the above distance squared = (xa-xb)^2 + (ya-yb)^2) d = xa^2 - 2*xa*xb + xb^2 + ya^2 - 2*ya*yb + yb^2 d = xa^2 - 2*xa*xb + xb^2 + ya^2 - 2*ya*yb + yb^2 d = ( xa^2 + xb^2 + ya^2 + yb^2 ) - 2*( xa*xb + ya*yb ) d = first-term - second-term The first-term is always positive and will always occur for all (x,y) pairs ( paired off as point a & point b ). Thus, we want the part of the second-term in parenthesis to be as positively large as possible !!! Thus, for all pairs of points a(x,y) & b(x,y), we want to choose the a-b pairs that cause the sum of all pairs to be as large as possible. ie. If we can sum all pairs, a(x,y) & b(x,y) and Maximize the value of: xa*xb + ya*yb , we will have an answer!!! So... given a bunch of points (xi,yi), how do we pair them up such that for each pair of points, a(x,y) & b(x,y), we get a maximum value of xa*xb + ya*yb ??? If you solve this algorithm.... I think you have a solution. Is it easier this way? I'm not really sure. Dan :-) -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
