摘要
Given a set of points V in the plane, the Euclidean bottleneck matching problem is to match each point with some other point such that the longest Euclidean distance between matched points, resulting from this matching, is minimized. To solve this problem, we define k-relative neighborhood graphs, (kRNG) which are derived from Toussaint's relative neighborhood graphs (RNG). Two points are called k-relative neighbors if and only if there are less than k points of V which are closer to both of the two points than the two points are to each other. A kRNG is an undirected graph (V, E <sub>r</sub> <sup>k</sup> ) where E <sub>r</sub> <sup>k</sup> is the set of pairs of points of V which are k-relative neighbors. We prove that there exists an optimal solution of the Euclidean bottleneck matching problem which is a subset of E <sub>r</sub> <sup>17</sup> . We also prove that |E <sub>r</sub> <sup>k</sup> | < 18 kn where n is the number of points in set V. Our algorithm would construct a 17RNG first. This takes O(n <sup>2</sup> ) time. We then use Gabow and Tarjan's bottleneck maximum cardinality matching algorithm for general graphs whose time-complexity is O((n log n) <sup>0.5</sup> m), where m is the number of edges in the graph, to solve the bottleneck maximum cardinality matching problem in the 17RNG. This takes O(n <sup>1.5</sup> log <sup>0.5</sup> n) time. The total time-complexity of our algorithm for the Euclidean bottleneck matching problem is O(n <sup>2</sup> +n <sup>1.5</sup> log <sup>0.5</sup> n). © 1992 Springer-Verlag New York Inc.