Partitioning heuristics for two geometric maximization problems (Q800827)

Given n points randomly selected from a uniform distribution on the unit square, we describe linear-time partitioning heuristics which will construct a matching or a tour of these points. We show that the heuristics closely approximate the optimum values as \(n\to \infty\). Hence we show that the asymptotic values of the maximum matching and tour are about 0.3826n and twice this value respectively.