We study an old geometric optimization problem in the plane. Given a perfect matching @math on a set of @math points in the plane, we can transform it to a non-crossing perfect matching by a finite sequence of flip operations. The flip operation removes two crossing edges from @math and adds two non-crossing edges. Let @math and @math denote the minimum and maximum lengths of a flip sequence on @math , respectively. It has been proved by Bonnet and Miltzow (2016) that @math and by van Leeuwen and Schoone (1980) that @math . We prove that @math where @math is the spread of the point set, which is defined as the ratio between the longest and the shortest pairwise distances. This improves the previous bound if the point set has sublinear spread. For a matching @math on @math points in convex position we prove that @math and @math ; these bounds are tight. Any bound on @math carries over to the bichromatic setting, while this is not necessarily true for @math . Let @math be a bichromatic matching. The best known upper bound for @math is the same as for @math , which is essentially @math . We prove that @math for points in convex position, and @math for semi-collinear points. The flip operation can also be defined on spanning trees. For a spanning tree @math on a convex point set we show that @math .
@cite_0: A perfect straight-line matching @math on a finite set @math of points in the plane is a set of segments such that each point in @math is an endpoint of exactly one segment. @math is non-crossing if no two segments in @math cross each other. Given a perfect straight-line matching @math with at least one crossing, we can remove this crossing by a flip operation. The flip operation removes two crossing segments on a point set @math and adds two non-crossing segments to attain a new perfect matching @math . It is well known that after a finite number of flips, a non-crossing matching is attained and no further flip is possible. However, prior to this work, no non-trivial upper bound on the number of flips was known. If @math (resp. @math ) is the maximum length of the longest (resp. shortest) sequence of flips starting from any matching of size @math , we show that @math and @math (resp. @math and @math ).
The @math upper bound of Theorem carries over to perfect matchings. As for lower bounds, Bonnet and Miltzow @cite_0 presented two matchings @math and @math such that @math and @math . The bound @math holds even if @math is a bichromatic matching, while the proof of @math does not generalize for the bichromatic setting.