A new algorithm:

We present a new fast, approximate algorithm for Matching two set of points in the plane. Empirically, it produces an average error of 8% compared with the best solution. Thus it is appropriate for very large sets where approximate Bipartite Matching is tolerable.

Bipartite Matching is defined as follow: Given two sets of points P and Q such that |Q|=|P|, find a one-to-one mapping between the two sets of points that minimizes total distances. When using our applets for Bipartite Matching, use a resolution of 1024x768 pixels.

Closest Match, Remove Intersections and Remove Long Edges:

The applet consists of several algorithms:

1 - The Closest Matching (CM) algorithm is a new algorithm to match the points based on the Voronoi Diagram construction. Construction is followed by a Remove Longe Edges (RLE) algorithm which removes the long edges produced by the algorithm CM and Remove Intersection (RI) which removes the intersection between the segments. For more details you may contact us;

The Minimum Weight Bipartite Perfect Matching (minimize total weight):

2 - The Minimum Weight Perfect Matching (MWM) finds the best way to marry all the black points to the red points using the minimum total line length. The algorithm is based on some work in Geometric Duality and Combinatorial Optimization by M. Juenger, Universitaet zu Koeln and W.R. Pulleyblank, IBM T. J. Watson Research Center; A special thanks to the authors of the java code Michael Maguire and Luis Goddyn.

The Bottleneck Matching (minimize max distance):

3 - The Bottleneck Matching (BNM) algorithm's purpose is to find a matching between the two sets such that the length of the longest edge is minimized. The implementation is based on the paper by A. Efrat, A. Itai "Improvements on Bottleneck Matching and Related Problems Using Geometry", in Proceedings of the 12th ACM Symposium on Computational Geometry. 

Settings:

Before running the algorithm (CM) you should click on the button Transfer Barycenter. From the window Result you can see useful information about how each algorithm performs. The others options are: Voronoi Diagram, Delaunay Triangulation, Convex Hull, Intersections Animation, Show Match and view algorithm step by step.

Execution times compared with exact solutions (seconds):

In the Table on the left, the running time of the proposed algorithm is compared to that of the Minimum Weight Matching algorithms (The input stations are generated uniformly and randomly). For example, to reassign 1000 mobile base stations would require about 30 minutes using the Minimum Weight Matching algorithm whereas our algorithm takes less than 3 seconds. On the other hand our proposed solution gives only an 8% error in the average case, and only 10% error in the worst case. These timing and accuracy results continue to hold when the input is generated by a clustering algorithm.

Average error on random input compared with MWM:

Our proposed solution gives only an 8% average error with respect to the optimal minimum weight matching. The maximum error is at most 10%. Moreover the maximum distance, corresponding to the time needed to the simultaneous base stations move, is lower than the one returned by the Minimum Weight Matching. These results are illustrated in the next diagrams: