Graph Theory – Connecting $2n$ Points in $\mathbb R^2$ with Line Segments

algorithmscombinatorial-optimizationgraph theorylinear programmingperfect-matchings

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.

Best Answer

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$.

Related Question