Connected Matchings

We show that each set of n≥ 2 points in the plane in general position has a straight-line matching with at least $(5n+1)/27$ edges whose segments form a connected set, and such a matching can be computed in O(n log n) time. As an upper bound, we show that for some planar point sets in general position the largest matching whose segments form a connected set has n-1/3 edges. We also consider a colored version, where each edge of the matching should connect points with different colors.