I have two sets of points plotted in a coordinate system. Each point in a set must be matched to *at least* one point at the other set, in a way that the sum of the length of the lines drawn by joining those points should be as low as possible. To make it clear, line drawing is just an abstraction, the actual output is just the pairs of points that must be matched.

I've seen this question about a similar problem, except that in my case there's no single-link restriction since the sets may have different sizes. Is there any kind of problem that describes this situation? More specifically, what algorithm could I use to solve this, assuming each set may have a maximum of 10 points?

You can model this as a network flow problem.

By having a source of 1 at each point in the first set, and a sink of 1 at each point in the second set, plus an extra node 'dest' for any left over capacity, any valid flow will always connect every point.

Make edges between the points with cost according to the distance between the points.

So far we have a network whose solution will be the lowest cost matching of set 1 to set 2 (i.e. each point will have a single link).

To allow multiple links you can simply make the following additions:

- add 0 weight edges between each point in set2 and 'dest' (this allows points in set 2 to be multiply connected)
- add 0 weight edges between 'dest' and each point in set2 (this allows points in set 1 to be multiply connected)

```
import networkx as nx
import random
G=nx.DiGraph()
set1=['A','B','C','D','E','F','G','H','I']
set2=['a','b','c']
# Assume set1 > set2 (or swap sets)
assert len(set1)>=len(set2)
G.add_node('dest',demand=len(set1)-len(set2))
A=[]
for person in set1:
G.add_node(person,demand=-1)
G.add_edge('dest',person,weight=0)
for project in set2:
cost = random.randint(1,10) # Assign appropriate costs here
G.add_edge(person,project,weight=cost) # Edge taken if person does this project
for project in set2:
G.add_node(project,demand=1)
G.add_edge(project,'dest',weight=0)
flowdict = nx.min_cost_flow(G)
for person in set1:
for project,flow in flowdict[person].items():
if flow:
print person,'->',project
```

You can use a discrete optimization approach (Integer Programming).

We have two sets A, of size X, and B, of size Y. This means a maximum of X*Y links, each described by a boolean variable: L(i,j) = L(Y*i+j) is 1 if nodes A(i) and B(j) are linked, 0 if not. If X = Y = 10, we can write link L(7,3) as L73.

We can rewrite the problem like this:

Node A(i) has at least one link: X (say, ten) criteria with i from 0 to X-1, each of them comprised of Y components:

```
L(i,0)+L(i,1)+L(i,2)+...+L(i,Y-1) >= 1
Node B(j) has at least one link, and there are Y criteria made up of X components:
L(0,j)+L(1,j)+L(2,j)+...+L(X-1,j) >= 1
```

The minimal cost requirement becomes:

```
cost = SUM(C(0,0)*L(0,0)+C(0,1)*L(0,1)+...+C(9,9)*L(9,9)
```

With these conventions, we can easily build the matrices for an ILP problem, that can be passed to our favorite ILP solving package or library (C, Java, Python, even PHP).

====

A self-contained "greedy" algorithm which is **not** guaranteed to find a minimum, but is reasonably quick and *should* give reasonable results unless you feed it a pathological data set, is:

```
- connect all points in the smaller set, each to its nearest point in the other set.
- connect all unconnected points remaining in the larger set, each to its
nearest point in the first set, whether it's already connected or not.
```

As an optimization, you can then enumerate the points in the larger data set; if one of them (say A) is singly connected to a point in the first data set (say B) which is multiply connected, and is not its nearest neighbour C, you can switch the link from A-B to A-C. This takes care of one of the simplest problems that may arise from the "greediness" of the algorithm.

Similar Questions

As far as I can tell (and correct me if I'm wrong), if you want to have graphical buttons that look good (with nice anti-aliasing) on multiple sized devices, you have to create different a set of diff

To find if the point is on a specified line containing two points i do the following checks: -(Boolean)isOnLine:(Line*) line point:(CGPoint) point{ //If between two dots: if (((line.first.x <= poin

How to find the minimum perpendicular distance of point from a line in 3D plane? Please give me the logic and I will try to code on myself. Please let me know how to do it in terms of x,y,z that is in

Example: This is just\na simple sentence. I want to match every character between This is and sentence. Line breaks should be ignored. I can't figure out, what the correct syntax is.

I have two data sets, AAPL and AMZN, that I wish two merge but find it difficult to do so as merge cbind fail to do as I desire it to be. I believe the issues is recognizing the data sets as data.fram

I got two sets of points S and V, both have the size n. I want to link the two sets so that every point in S links to one and only one point in V. The cost to link two points is defined as the Euclide

I have two sets of 2D points, separated from each other by a line in the plane. I'd like to efficiently find the pair of points, consisting of one point from each set, with the minimum distance betwee

I want to compare one value against all values in the other array and extact a match. These are different in length. Imagine one column of unsorted ID's and one column of ID's and names. I came up wit

I need to find matching between two independent sets of features extracted from two images of the same scene captured by two different cameras. I'm using the HumanEvaI data set, so I have the calibrat

I need to compare two different arrays in Matlab. It's going to be used for a Yahtzee game. If I have an array that contains [1 2 3 4] and an array that contains [1 2 3 4 5], how do I check if the fir

I have two Eclipse working sets (WorkingSet 0.1.x and WorkingSet 0.2.x). I need to do work on them interchangeably, though neither interacts with the other. The problem is that some of the projects ob

We have some intervals for example [1;4] [7;13] [9;14] inputs should return 3+6+1=10. Is there any way using segment trees to find the total length of these intervals when the intervals can be dynamic

i have two 1D numpy arrays. The lengths are unequal. I want to make pairs (array1_elemnt,array2_element) of the elements which are close to each other. Lets consider following example a = [1,2,3,8,20

I've been trying to rotate a bunch of lines by 90 degrees (that together form a polyline). Each line contains two vertices, say (x1, y1) and (x2, y2). What I'm currently trying to do is rotate around

Please help me! I need to find sum of the elements of two lists of different length. It should look like: ?-p([1,2,3],[1,2,3,9],L),write(L),nl. L = [2,4,6,9]. p([],_,[]). p(_,[],[]). p([H1|T1],[H2|T2]

Assume two sets (unordered, no duplicate elements): A = set([z, x, c]) B = set([x, z, d, e]) These sets have two common elements: z and x, and some set-specific elements: c, d, e. H

What is the disadvantage to using a MySQL longtext sized field when every entry will fit within a mediumtext sized field? The reason I am asking is because I have some longtext sized fields and recent

I'm using Font Awesome icons, and I'd like them to have a background. The problem is that the icons are different sized so padding will not result equal sized boxes. Setting the width and height as a

We have K different sets of numbers. We have to choose a number from each set, so that the difference between the higher and the lower number is the minimum. Any ideas?

How can i find out if a Point(x,y) is on a the Line created between two other Points? I tried this but something seems to be wrong, as i don't get the results i should. public boolean intersects(Point

I need to be able to build two different versions of my GWT application using two different sets of property values. For example, one version would be built with the value of custom_property set to A

How do I get the minimum width of images that are in a folder images/list? The folder has different sized images and I just want the minimum width so as to set all images and display a proper layout

Is there an easy way to strip out all instances of: console.log(items); Where items is a string that's always different (different length, different text)?

I have a requirement to show data on a line jqPlot with two different scales (meters and feet). I have multiple lines/data sets on the same plot and also have a jQuery toggle which will switch the dat

I have two sets, each set is a listing of a pair of numbers Set1 =[(x1, y1), (x2, y2), ..., (xN, yN)] Set2 =[(a1, b1), (a2, b2), ..., (aN, bN)] If plotted on an XY plane, Set1 and Set2 have the same

Hi every one .. in my application I have succeeded draw line between two images code give below but i want to match two images between two column when images matched i want to show a toast message.Jus

Hi guys The following xpath does not seem to work. //FullName[sum(string-length(FirstName) | string-length(LastName))>= 30] Error: Expression must evaluate to a node-set. XML snippet <FullName&

Is there a way to specify a regular expression to match every 2nd occurrence of a pattern in a string? Examples searching for a against string abcdabcd should find one occurrence at position 5 search

I have a range of values (L,R,U,D) and two variables, d and newd, containing one of them. I need to check if d and newd are in the same subset (L,R or U,D) or not. I know I can do this: d in {'L','R'}

I have two sets each containing x,y coordinates for a series of points and codes respectively. Considering the huge sizes of files I'm looking for an optimized way in Matlab to connect each point fro

I am looking for association mining algorithm where I can mine frequent item sets of length 2 only. Is it better to use a query on database to compute frequent items when stopping at 2-itemsets.

I want to get the total offSetTop and the total offSetLeft of a child element which have many level of parent element and may be adding up. Is that any shorthand way, besides of adding one by one in

I'm trying to make a function that compares two different length arrays to each other and if they match then some actions are performed. Array1, cell1 compares to array2, cell1, cell2, cellN... Then A

I'm trying to reference two primary keys from two different tables, but the problem is that they don't match due to its character length. For an example , person.personid = '1234' and department.pers

I am writing the following code that finds a match from one worksheet (Sheet2) and pastes values into (sheet2). So far the code targets those names that have accepted as offset values. it loops thro

Which of these two is more efficient in Erlang? This: ValueA = MyRecord#my_record.value_a, ValueB = MyRecord#my_record.value_b. Or this: {ValueA, ValueB} = {MyRecord#my_record.value_a, MyRecord#my_re

How can I write a regex for alphanumeric chars allowing one or two stars and restricting the total string length to 3. Ex : the below strings length is 3 *12 or *2* 0r *a* or *B* or **2 So, the * sym

Is there any client side javascript code which can validate the minimum word length in CKEditor. For e.g. setting that a minimum of 500 words are required before the form can be submitted. I tried a f

I have two tables in my Report. Both use two separate Data Sets, which get data from the same Stored Procedure. Now, I want the data sets to get different data based on different parameter values. Is

I have an Orders table containing column CreatedDate (datetime) on when the order took place. Today is Feb 13, 2014. How to get total records for the last 4 weeks for every week. it should return so

Lets say I have a web site hosted on a computer named linux and it is part of two different networks with the addresses 192.168.1.1 and 10.1.1.1. When working locally on linux, I can access this w

I need to compare the values stored in two variables.The variable sizes are different. For example x = c(1,2,3,4,5,6,7,8,9,10) and y = c(2,6,11,12,13) I need an answer that 2 and 6 are present in

Would someone please share their implementation of having separate error messages for minimum and maximum string length using data annotations in MVC? It seems StringLength only allows a single error

I want to be able to extract two sets of data in one script with a total of 15 records. In my scenario, I extract members from a certain town which for example could return 3 records, and then I want

I need to synchronize two large sets of strings in Java, one of the on the client and the other on the server. Most probably the client is missing a couple of entries which it should receive from the

Two .NET apps run on the same machine simultaneously and are able to communicate with each other. Clicking a button in one app must trigger both apps to restart themselves with different command line

Given two std::sets, one can simply iterate through both sets simultaneously and compare the elements, resulting in linear complexity. This doesn't work for std::unordered_sets, because the elements m

I have two sets and need to create a third one, which will include elements from the first one that are absent in the second one: (? #{a b c} #{b}) ; -> [a c] I know about disj, but it

I'm asked to write a program to add a byte sized array elements. First 2 bytes are the number of elements in the array. The array may contain thousands of numbers so I should put the sum in 32-bit reg

I am having issues with a couple arrays below and the match method. On my page I call the Checkout() function and it sets a temporary array equal to the array I've been building with different options