On geometric matching
Odile Marcotte, Subhash Suri · 1989
An Ο(n3/2√α(n)) time algorithm is presented for finding a minimum-weight matching of a set of 2n points lying on the boundary of a convex polygon, where α(n) is the functional inverse of the Ackerman's function. Generalizing this result, we obtain an Ο(n3/2 logn√α(n)) time algorithm for the minimum-weight matching of points lying on the boundary of a simple nonconvex polygon, where we require that the line segments joining the matched pairs be contained within the polygon. We also consider the maximum-weight matching problem, and obtain algorithms of complexities Ο(n) and Ο(n log n) for the convex and the nonconvex case, respectively. By contrast, finding a weighted matching of an arbitrary set of points takes Ο(n5/2 log4 n) time [Vaidya 1987].