# Algorithm for finding the set of minimum coordinate pairs

Consider these two sets of coordinate pairs with weights:

| set 1           |    | set 2           |
| (1,0) - (0,1) 1 |    | (1,1) - (1,1) 2 |
| (0,1) - (1,1) 4 |    | (0,0) - (0,0) 1 |
| (1,1) - (0,0) 3 |    | (1,0) - (1,0) 3 |
| (0,0) - (1,0) 8 |    | (0,1) - (0,1) 6 |


Each set has the properties:

1. A coordinate is a 2-tuple, which is a point in a Euclidean plane, more specifically it is the position of each element of a square matrix M (in this case 2x2):

[[(0, 0), (0, 1)],
[(1, 0), (1, 1)]]

2. Coordinate pairs define a 1:1 unique mapping from one matrix m1 to another m2. Both matrices have the same dimensions.

The objective is to find a configuration from multiple sets of such coordinate pairs so that the properties above are not violated (e.g. (0,0) - (1,1) and (1,0) - (1,1) would be a violation), and that the best minimum possible is found for each coordinate pair, this can be thought of as the finding coordinate pairs such that the overall sum of the weights is minimized.

Solution (trivial):

| (1,1) - (1,1) 2 |
| (0,0) - (0,0) 1 |
| (1,0) - (1,0) 3 |
| (0,1) - (0,1) 6 |


What I would like to know if there is a specific name for this kind of problem (I suspect it is a combinatorial type problem), and if there is, is there a known algorithm for achieving this efficiently?

• You seem to be specifying a permutation, if between 2-tuples and not natural numbers. – greybeard Nov 24 '16 at 22:14
• I can't understand the question. You define a coordinate in terms of the word coordinate ("A coordinate is... the coordinate of..."); I don't know what that means. I don't know how matrix $M. How does the matrix relate to the "coordinate pairs" or to the set? I don't understand what you mean by property 2. How does a single "coordinate pair" define a mapping from one matrix to another? I don't understand what you mean by "the best minimum possible". What is the input to the algorithm, and what is the desired output? – D.W. Nov 24 '16 at 22:35 • I've redefined a coordinate in term of the position of a matrix element. " I don't know how matrix$M" - what do you mean here? In property 2 I say that coordinate pairs (as seen above) define a mapping, not that a single coordinate pair defines a mapping. The input is the first two sets at the beginning of the question, the output would be the set and the end of the question. I'll edit the question to perhaps define the best minimum possible per coordinate pair in terms of the overall sum of the weights. – user1658296 Nov 25 '16 at 7:15
• 1. I understand what it means to say that a coordinate is a point in a Euclidean plane. I don't understand it means to say that a coordinate is "the position of each element of a square matrix M". Can you edit the question to explain what that means in a bit more detail? Can you give a clearer example? 2. I don't understand how coordinate pairs define a 1:1 unique mapping from one matrix m1 to another m2. You make this claim, but you don't justify or explain. Can you edit the question to describe how it defines a mapping? What is the mapping, exactly? – D.W. Nov 25 '16 at 16:57
• 3. What do you mean by "a configuration"? You don't define that term. Overall sum of the weights -- of which weights? – D.W. Nov 25 '16 at 16:57