Heuristics for planar minimum‐weight perfect metchings

Abstract

Abstract Several linear‐time approximation algorithms for the minimum‐weight perfect matching in a plane are proposed, and their worst‐ and average‐case behaviors are analyzed theoretically as well as experimentally. A linear‐time approximation algorithm, named the “spiral‐rack algorithm (with preprocess and with tour),” is recommended for practical purposes. This algorithm is successfully applied to the drawing of road maps such as that of the Tokyo city area.