Minimum Matching on the Minimum Triangulation

29 Views Asked by At

Consider $N$ uniformly random points on a torus. Consider only Euclidean distances.

Does the length of the minimum matching on the minimum length triangulation of the points differ from the length of the minimum matching itself by a factor which is $\mathcal{O}(1)$?

Given the randomness, I would expect that, on average, they differ by a constant factor, despite the ability to construct a point set whose minimum triangulation misses out edges from the minimum matching.