Advanced Search

A partitioning algorithm for the Euclidean matching problem in ${ℝ}^d$ is introduced and analyzed in a probabilistic model. The algorithm uses elements from the fixed dissection algorithm of Karp and Steele (1985) and the Zig-Zag algorithm of Halton and Terada (1982) for the traveling salesman problem. The algorithm runs in expected time $n{\left(logn\right)}^{p-1}$ and approximates the optimal matching in the probabilistic sense.