Stochastic analysis of partitioning algorithms for matching problems

Partitioning algorithms for the Euclidean matching and for the semi-matchin g problem in the plane are introduced and analysed. The algorithms are anal ogues of Karp's well-known dissection algorithm for the travelling salesman problem. The algorithms are proved to run in time n log n and to approxima te the optimal matching in the probabilistic sense. The analysis is based o n the techniques developed in Karp (1977) and on the limit theorem of Redmo nd and Yukich (1993) for quasiadditive functionals.