Stack Overflow Asked by Sonya gold on January 15, 2021
I’m trying to find an efficient algorithm for the following problem:
Given two different sets, both of size N. Each element in the two sets has coordinates (x,y).
The task is to optimize the pairings between these two sets such that the maximum distance between the paired elements given a pairing, is minimized.
I have only found algorithms that deal with the squared sum of all distances between paired elements or the smallest distance between any two points from the two different sets.
Any idea how can this be achieved in reasonable run time? or name an algorithm that might help here.
For example:
Given a list of N pair of points that are associated with locations – (x0,y0), (x1,y1), (x2,y2)….( xn-1,yn-1), name them a0,a1,a2…aN-1 accordingly
And another list of N pairs of different points (locations)
(x0,y0), (x1,y1), (x2,y2)….( xn-1,yn-1), name them b0,b1,b2…bN-1 accordingly
How can I pair all elements (each element is a pair of points) from list 1 (a0,a1,a2…aN-1) to the other elements in list 2 (b0,b1,b2…bN-1) so that we chose the shortest distances? eventually, we’d need to print the maximum distance among all minimum distances we have found for each of the elements.
Thanks
Get help from others!
Recent Answers
Recent Questions
© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP