Technical Report CS0865

TR#:CS0865
Class:CS
Title: IMPROVEMENTS ON BOTTLENECK MATCHING USING GEOMETRY.
Authors: E. Efrat and A. Itai
PDFCS0865.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$.
CopyrightThe 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.

To the list of the CS technical reports of 1995
To the main CS technical reports page

Computer science department, Technion
admin