A Fast Heuristic Based on Spacefilling Curves for Minimum-Weight Matching in the Plane,
GEORGIA INST OF TECH ATLANTA PRODUCTION AND DISTRIBUTION RESEARCH CENTER
Pagination or Media Count:
The authors present a heuristic to find a good matching on n points in the plane. It is essentially sorting and so runs in On log n time worst case or linear expected time. Its performance is competitive with that of previously suggested methods. However, it has the advantages of being trivial to code and of being indifferent to the choice of metric or the probability distribution from which the points are drawn.
- Theoretical Mathematics