Improving Sharir and Welzl's bound on crossing-free matchings through solving a stronger recurrence

Abstract

Sharir and Welzl [1] derived a bound on crossing-free matchings primarily based on solving a recurrence based on the size of the matchings. We show that the recurrence given in Lemma 2.3 in Sharir and Welzl can be improve to $(2n-6s){\text{Ma}}_m(P)\le \frac{68}{3}(s+2){\text{Ma}}_{m-1}(P)$ and $(3n-7s){\text{Ma}}_m(P)\le 44.5(s+2){\text{Ma}}_{m-1}(P)$, thereby improving the upper bound for crossing-free matchings.