Fast efficient pairing of points for maximum total distance
A new O(n log n) approach for the Euclidean maximum weight matching problem
Computational Geometry
Summary
The problem is to pair up points so that the total distance between paired points is as large as possible. The authors introduce a new method that solves this problem much faster than previous best exact methods, running in n log n time instead of n to the 2.5 power. Their approach finds pairings very close or equal to the best possible on tested examples. This speed-up makes it practical to solve big problems where older exact methods would be too slow.
What this means in practice
- •For logistics planners: Generate efficient large-scale pairings between geographic locations to maximize total transport distances quickly, enabling better complex route designs.
- •For computer graphics developers: Optimize point pairing in geometric modeling tasks where large distance pairings improve visual or structural outcomes without costly computations.
Authors
Rostislav Staněk, Robert Arustamyan
Abstract
In a weighted graph $G = (V, E)$, the maximum weight matching problem (MWM) asks for a matching (i.e. pairing) of its vertices, such that each vertex is paired with at most one other vertex and the total sum of weights of all edges connecting paired vertices is maximised. If the vertices of the graph correspond to points in the Euclidean plane and the weights to their pairwise Euclidean distances, we get the Euclidean maximum weight matching problem (Euclidean MWM). The best optimum-solution algorithm for this problem runs in $O(n^{2.5})$. Furthermore, there exists an FPTAS guaranteeing a $(1 - ε)$-approximation ratio, which runs in $O(m ε^{-1} \log ε^{-1})$ time. Heuristics with a subquadratic running time (with respect to the number of vertices $|V|$) are known, but often yield solutions of a modest quality. In this paper, we present a novel algorithm for solving the Euclidean MWM running in $O(n \log n)$ time and providing excellent solution quality, especially for larger instances. In particular, in our computational tests, the algorithm yielded optimum or near-optimum solutions for all test instances; the worst observed optimality gap was less than $1.38\%$. This makes the algorithm highly attractive for practical applications, especially when exact methods become computationally prohibitive due to the size of the instance.