Connecting $2n$ points in $\mathbb R^2$ with line segments s.t. each point belongs to exactly one line segment

Question

I'm trying to do a certain simulation related to the toric code and I'm looking for an algorithm that connects $2n$ points ($n \in \mathbb Z_+$) in $\mathbb R^2$ with line segments with the following restrictions:

1. Length of the all segments joined together has to be minimal.
2. One point can be a part of only one line segment.
3. Line segments cannot intersect.

We can assume that the $2n$ points all lie on a square grid as shown in the following figure.

Someone on Stack Overflow considered a similar question but the answers there are not really satisfying or authoritative. However, I will reuse the picture from there to clarify what I want:

Is there a reasonable non-brute force algorithm for this problem? I wonder if the Travelling Salesman Problem can somehow be modified to fit this situation. Someone also mentioned K-means clustering on the Stack Overflow question but I'm not sure how that's relevant.

Answer 1

You can solve this as a minimum-weight perfect matching problem in a graph with a node for each point and an edge for each pair of points. Because the distances satisfy the triangle inequality, an optimal solution will naturally avoid intersecting line segments. You can solve the problem with a specialized algorithm or via integer linear programming with a binary variable $x_{ij}$ for each edge and a linear constraint $\sum_{i,j:k\in\{i,j\}} x_{ij} = 1$ for each node $k$.

Answer 2

@RobPratt's answer describes a good general-purpose approach. The specific case where edge weights are given by Euclidean distances is also a well-studied problem. The paper A Divide-and-Conquer Algorithm for Min-Cost Perfect Matching in the Plane by Varadarajan solves this problem in $O(n^{3/2} \log^5 n)$ time.