Hi, I think we could model this problem as a constraint problem and then use Integer linear programming to solve the same. You can find the solution to a similar problem here.
http://www.ee.ucla.edu/ee236a/lectures/intlp.pdf Regards On Wed, Feb 17, 2010 at 8:54 AM, Dan <dant...@aol.com> wrote: > 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 algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.