10.1007/bf01758842
doi
Given a set of pointsV 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 definek-relative neighborhood graphs, (kRNG) which are derived from Toussaint's relative neighborhood graphs (RNG). Two points are calledk-relative neighbors if and only if there are less thank points ofV which are closer to both of the two points than the two points are to each other. AkRNG is an undirected graph (V,Erk) whereErk is the set of pairs of points ofV which arek-relative neighbors. We prove that there exists an optimal solution of the Euclidean bottleneck matching problem which is a subset ofEr17. We also prove that ¦Erk¦ < 18kn wheren is the number of points in setV. Our algorithm would construct a 17RNG first. This takesO(n2) time. We then use Gabow and Tarjan's bottleneck maximum cardinality matching algorithm for general graphs whose time-complexity isO((n logn)0.5m), wherem is the number of edges in the graph, to solve the bottleneck maximum cardinality matching problem in the 17RNG. This takesO(n1.5 log0.5n) time. The total time-complexity of our algorithm for the Euclidean bottleneck matching problem isO(n2 +n1.5 log0.5n).
https://scigraph.springernature.com/explorer/license/
articles
1992-12
177-194
Solving the Euclidean bottleneck matching problem byk-relative neighborhood graphs
http://link.springer.com/10.1007/BF01758842
false
1992-12-01
2019-04-11T09:53
research_article
en
Chang
M. S.
C. Y.
Tang
National Tsing Hua University
Institute of Computer Science, National Tsing Hua University, 30043, Hsinchu, Taiwan, Republic of China
pub.1036591041
dimensions_id
0178-4617
Algorithmica
1432-0541
Academia Sinica
Academia Sinica, Taipei, Taiwan, Republic of China
National Tsing Hua University, Hsinchu, Taiwan
1-6
R. C. T.
Lee
Institute of Computer Science and Information Engineering, National Chung Cheng University, 62107, Chiayi, Taiwan, Republic of China
National Chung Cheng University
Computation Theory and Mathematics
8
readcube_id
ae4e49e1e25feb22f7a424ca25759580a5617d1da5b4f54ef40738c43f634130
Springer Nature - SN SciGraph project
Information and Computing Sciences