Probabilistic Analysis of a Greedy Heuristic for Euclidean Matching
David Avis, Burgess Davis, John M. Steele · Probability in the Engineering and Informational Sciences · 1988
Given a collection of n points in the plane, the Euclidean matching problem is the task of decomposing the collection into matched pairs connected by line segments in such a way as to minimize the sum of all the segment lengths. The greedy heuristic provides an approximate solution to the Euclidean matching problem by successively matching the two closest unmatched points. We study the behavior of Gn, the sum of the lengths of the segments produced by the greedy heuristic.