# Technical Report CS0865

 TR#: CS0865 Class: CS Title: IMPROVEMENTS ON BOTTLENECK MATCHING USING GEOMETRY. Authors: E. Efrat and A. Itai PDF CS0865.pdf Abstract: Let $A$ and $B$ be two sets of $n$ points in the plane. We present an $O(n^{1.5+\epsilon}$ time algorithm that matches the points of $A$ to the points of $B$ such that the distance between the farthest matched pair is minimal. Let the {\em length} of the matching denote this distance. We also show that our algorithm can be applied when $A$ and $B$ are point-sets in $R^d$ and the distance is measured using the $L_{\infty}$ norm. This technique can be used to find in time $O(n^{5+\epsilon}$ a translation of $B$ for which the distance of its matching to $A$ is smaller than a pre-determined parameter $\rho$, (or deduce, that no such matching exist). This improves the previous result of Alt et al. [4] by a factor of nearly $n$. Copyright The above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/1995/CS/CS0865), rather than to the URL of the PDF files directly. The latter URLs may change without notice.