Crossing-Free Perfect Matchings in Wheel Point Sets

Consider a planar finite point set P, no three points on a line and exactly one point not extreme in P. We call this a wheel set and we are interested in pm(P), the number of crossing-free perfect matchings on P. (If, contrary to our assumption, all points in a set S are extreme, i.e. in convex position, then it is well-known that pm(S) = C m , the mth Catalan number, m : = | S | 2 $$m:= \frac{\vert S\vert } {2}$$ .) We give exact tight upper and lower bounds on pm(P) depending on the cardinality of the wheel set P. Simplified to its asymptotics in terms of C m , these yield 9 8 C m ( 1 + o ( 1 ) ) ≤ p m ( P ) ≤ 3 2 C m ( 1 + o ( 1 ) ) m : = | P | 2 . $$\displaystyle{ \frac{9} {8}C_{m}(1 + o(1)) \leq \mathsf{pm}(P) \leq \frac{3} {2}C_{m}(1 + o(1))\,m:= \frac{\vert P\vert } {2}. }$$ We characterize the wheel sets (order types) which maximize or minimize pm(P). Moreover, among all sets S of a given size not in convex position, pm(S) is minimized for some wheel set. Therefore, leaving convex position increases the number of crossing-free perfect matchings by at least a factor of 9 8 $$\frac{9} {8}$$ (in the limit as | S | grows). We can also show that pm(P) can be computed efficiently. A connection to origin embracing triangles is briefly discussed.