Lets say that i have a set of points (an even number of points). Is there any algorithm that lets me divide them into pairs so that the sum of the distances between the two points in each pair will be minimum? Thanks.

interesting

just put them all into a KD tree then find the nearest neighbor for each point?

oh, I see, the difficulty is that a given point's nearest neighbor, might in turn have something Ese as its own nearest, thus theres a choice between which pairs in a chain of 'nearests' to pair up...

IE, given a chain of points where A near B, B near C, C near D
you can choose AB CD
or xA BC Dy
...
basically a chain of one-directional 'nearests' relations have be paired up as 'even' or 'odd' pairs

and it gets even more complex conidering that such chains can merge...

Even so, intuitively I can see that theres a space partitioning tree concept involved here with the neighbor chaining...
your algo probably will involve identifying these neighbor chains and how they merge into a full tree
then some recursive trasversal of that tree to make pairs...

I have no idea how to solve your problem, but you can get a mediocre solution by finding the nearest point to each point and then pairing up points that have each other as their nearest points. Then you remove those points from the list and repeat the process until all the points are paired up. It's nowhere near the true minimum, but it seems to give me mostly short lines(with only a couple not so short lines). Given 1000 random points in a 500 by 500 area I get between 6000 and 6500 total distance.

There are a lot of algorithms for that problem, but I dont know if any of them is optimal except the greedy one.

I believe that class of problems is called "least squares clustering", you can google for that and you will find several references. In your case, you have the additionnal constraint of having exactly N/2 clusters of 2 points.

Do you need an optimal solution, or just a good one?

Quote: Original post by daniel_i_l
Lets say that i have a set of points (an even number of points). Is there any algorithm that lets me divide them into pairs so that the sum of the distances between the two points in each pair will be minimum?
Thanks.

Yes, there is an algorithm that does that: try all possible pairings (there are (2n)!/(n!*2^n) of them) and pick the one that has a smallest sum of distances. This can be organized in something like a tree search. The question then is if that's good enough or you need something faster. With a little memory, you can speed it up significantly, although the time it takes would still be exponential. Then you can start with some approximated solution and use it as a bound to abort branches that are guaranteed to have a larger sum of distances than the bound. Or maybe the approximated solution is good enough for your purpose and you should look for something like simulated annealing...

In any case, you didn't say much about your requirements. If the question is strictly whether an algorithm exists (computability), the answer is affirmative.

EDIT: Oh, and what is this question doing in the "Artificial Intelligence" forum?

[Edited by - alvaro on January 16, 2007 2:25:05 PM]

Quote: Original post by alvaro
EDIT: Oh, and what is this question doing in the "Artificial Intelligence" forum?

Maybe he's making a dating service for bots?

Doesn't bother me... seems like this kind of logic problem would be relevant to AI... I'm sure you can find a use for it somewhere...

It took a bit of searching, but I found the name of a slightly more general problem than this that has known polynomial time algorithms. Minimum weight perfect matching. Perfect matching = subgraph of a graph such that each vertex has exactly one edge. Minimum weight = the sum of the weights (in this case, distances between vertices) is minimal.

I'm not sure if there are better solutions available for when the graph is complete and/or uses euclidean distance or some other distance metric, but this shows there are at least polynomial time algorithms available for this problem.

Quote: Original post by alvaro
EDIT: Oh, and what is this question doing in the "Artificial Intelligence" forum?

It's quite closely related to loads of AI problems.

As a demonstration, let me paraphrase the original post:
"Lets say that i have an RTS game, with a set of workers and resources (an equal number of each). Is there any algorithm that lets me match workers to resources so that the sum of the time taken for workers to reach the resources will be the minimum?"

Quote: Original post by Kylotan

Quote: Original post by alvaro
EDIT: Oh, and what is this question doing in the "Artificial Intelligence" forum?

It's quite closely related to loads of AI problems.

As a demonstration, let me paraphrase the original post:
"Lets say that i have an RTS game, with a set of workers and resources (an equal number of each). Is there any algorithm that lets me match workers to resources so that the sum of the time taken for workers to reach the resources will be the minimum?"

Oh, that makes sense.

I found a library that seems to implement a solution to this problem. This is the relevant part of the documentation: http://www.algorithmic-solutions.info/leda_manual/mw_matching.html.

I think that latter problem (finding shortest distance set of connections between point set A and point set B) is a related but different problem - known as "Earth Mover's Distance" or EMD.