On the number of crossing-free matchings, cycles, and partitions

We show that a set of n points in the plane has at most O(10.05(n)) perfect matchings with crossing-free straight-line embedding. The expected number of perfect crossing-free matchings of a set of n points drawn independently and identically distributed from an arbitrary distribution in the plane is at most O(9.24(n)). Several related bounds are derived: ( a) The number of all ( not necessarily perfect) crossing-free matchings is at most O(10.43(n)). (b) The number of red-blue perfect crossing-free matchings ( where the points are colored red or blue and each edge of the matching must connect a red point with a blue point) is at most O(7.61(n)). ( c) The number of left-right perfect crossing-free matchings ( where the points are designated as left or right endpoints of the matching edges) is at most O(5.38(n)). (d) The number of perfect crossing-free matchings across a line ( where all the matching edges must cross a fixed halving line of the set) is at most 4(n). These bounds are employed to infer that a set of n points in the plane has at most O(86.81(n)) crossing-free spanning cycles ( simple polygonizations) and at most O(12.24(n)) crossing-free partitions ( these are partitions of the point set so that the convex hulls of the individual parts are pairwise disjoint). We also derive lower bounds for some of these quantities.