Hi!
I came across a bit difficult problem which I cannot cope with.
It says that in input there are two sets of points on plane (coordinates are given). The task is to assign points from one set to the points from another set in a way that no segment made form two points will intersect
Has anybody got idea how to solve it efficiently?
Thanks in advance.
Algorithm needed ;-)
Moderator: Board moderators
Polinomial solution
The next algorithm is surely polinomial but I am not sure that it is also efficient. Create a full bipartite graph from the points and give a cost for each edge as the length of the edge. If you make a minimum cost maximum matching on this graph the edges will not intersect themselfs.
It is an O(n^3) algorithm and it may be solved faster.
It is an O(n^3) algorithm and it may be solved faster.
First you can start from a random assignment and then try to find 2 segments A1B1 and A2B2 so that A1B1 + A2B2 > A1B2 + A2B1, then pair A1 with B2 and A2 with B!. By doing this you decrease the sum of all lengths of all pairs. As there are a finite number of different sums, after a while you have to stop. If two segments intersect then the sum of their lengths can be decreased by flipping the pairs of points. This solution is pretty fast in practice and very easy to implement.
Another solution is based on the fact that you can find a line that goes through a point from one set and a point from the other so that on it's left and also in it's right there will be a equal number of points from the two sets. For finding that line you must do a radial sweep around one point, and by doing this you split the problem in two parts. This algorithm is O(n^2 log n).
Another solution is based on the fact that you can find a line that goes through a point from one set and a point from the other so that on it's left and also in it's right there will be a equal number of points from the two sets. For finding that line you must do a radial sweep around one point, and by doing this you split the problem in two parts. This algorithm is O(n^2 log n).