Univ. of California San Diego (UCSD) Tech. Report 1994

Solving the Minimum-Cost Matching Problem for Quasi-Convex Tours: An Efficient ANSI C Implementation

Samuel R. Buss and Kirk G. Kanzelberger and David Robinson and Peter N. Yianilos

Abstract: We report an efficient and highly portable ANSI C implementation of the Buss-Yianilos minimum-cost matching algorithm for quasi-convex tours. A generic O(log n) time implementation of the required Omega predicate is included, resulting in worst-case O(n log n) runtime for arbitrary cost functions.

A constant-time Omega is provided for two special cases: the circle under Euclidean distance, and the real line where cost is defined as the square root of interpoint distance. In both of these settings, runtime is then O(n).

Code is also provided for circular tours with cost defined as the square root of angular distance (arclength). In this case, the generic Omega computation is employed.

The test programs generate pseudorandom node patterns. To ensure correctness, a straightforward O(n^3) dynamic programming solution may be optionally enabled, and the test programs will compare its result with that of the Buss-Yianilos algorithm.

As an additional option, the test programs produce PostScript-form graphical representations of the minimum-cost matchings found.

The performance of the package is reported for several modern RISC processors.


This manuscript also appeared as an NEC Research Institute Technical Report.