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 <[email protected]> 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 [email protected].
> To unsubscribe from this group, send email to
> [email protected]<algogeeks%[email protected]>
> .
> 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 [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.
