Accession Number:

ADA129857

Title:

A Fast Heuristic Based on Spacefilling Curves for Minimum-Weight Matching in the Plane,

Descriptive Note:

Corporate Author:

GEORGIA INST OF TECH ATLANTA PRODUCTION AND DISTRIBUTION RESEARCH CENTER

Report Date:

1983-04-01

Pagination or Media Count:

10.0

Abstract:

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.

Subject Categories:

  • Theoretical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE