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

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 O(n 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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Apr 01, 1983
Accession Number
ADA129857

Entities

People

  • John J. Bartholdi Iii
  • Loren K. Platzman

Organizations

  • Georgia Tech

Tags

Communities of Interest

  • Air Platforms

DTIC Thesaurus Topics

  • Algorithms
  • Engineering
  • Floating Point Operations
  • Industrial Engineering
  • Probability
  • Probability Distributions
  • Sequences
  • Square Roots
  • Systems Engineering

Readers

  • Operations Research
  • Regression Analysis.