Improvements on bottleneck matching and related problems using geometry
Alon Efrat, Alon Itai · 1996
Let A and B be two sets of n objects in R d , and let M be a (one-to-one) matching between A and B. Let min(M ), max(M ), and \\Sigma(M ) denote the length of the shortest edge, the length of the longest edge, and the sum of the lengths of the edges of M respectively. Bottleneck matching---a matching that minimizes max(M )---is suggested as a convenient way for measuring the resemblance between A and B. Several algorithms for computing, as well as approximating, this resemblance are proposed. The running time of all the algorithms involving planar objects is close to O(n 1:5 ). For instance, if the objects are points in the plane, the running time of the exact algorithm is O(n 1:5 log n). A semi-dynamic data-structure for answering containment problems for a set of congruent disks in the plane is developed. This data structure may be of independent interest. Next, the problem of finding a translation of B that maximizes the resemblance to A under the bottleneck matching criterion...