The Problem:
Given two sets of points A and B where the cardinality (size) of set A and B are equal, find a set S of pairs of points meeting the requirements defined below.
In the abstract "points" can be anything with a distance metric d, that is to say we can take two "points" p and q and d(p,q) == 0 if and only if p == q; d(p,q) == d(q,p); and triangle inequality.
Let the "cost" of a single pair (p,q) be d(p,q), that is let the "cost" be defined by the distance metric.
Let the "total cost" of the set S be the sum of the cost of all pairs in S.
1. Each pair in S is made up of one point from A and one point from B.
2. Each point in A is a member of exactly one pair in S.
3. Each point in B is a member of exactly one pair in S.
4. S minimizes the total cost.
A Concrete Example:
To make the problem concrete I'll simply define a skeleton, in C++, of a function that solves the problem:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | struct Vec3{ float x; float y; float z; }; struct Pair{ int i; int j; }; float distance(Vec3 p, Vec3 q){ p.x -= q.x; p.y -= q.y; p.z -= q.z; return(sqrtf(p.x*p.x + p.y*p.y + p.z*p.z)); } Pair *minimal_distance_pairing(Vec3 *a, Vec3 *b, int set_count){ Pair *result = (Pair*)malloc(set_count*sizeof(Pair)); // TODO: solve the problem return(result); } |
In this example we are given two sets of points in 3-dimensional euclidean space, with a euclidean distance metric, and want to pair off all the points while minimizing the total distance of the pairing.
I am interested both in both the euclidean version, and the fully abstract version, so whatever thoughts anyone wants to offer on either variant are welcome!