Andrei Asinowski and Günter Rote:

Point sets with many non-crossing matchings

Computational Geometry, Theory and Applications 68 (2018), 7–33. doi:10.1016/j.comgeo.2017.05.006, arXiv:1502.04925 [cs.CG].


The maximum number of non-crossing straight-line perfect matchings that a set of n points in the plane can have is known to be O(10.0438n) and Ω*(3n), where the Ω* notation hides polynomial factors in the aymptotic expression. The lower bound, due to García, Noy, and Tejel (2000), is attained by the double chain, which has Θ(3n/nΘ(1)) such matchings. We reprove this bound in a simplified way that uses the novel notion of down-free matchings. We then apply this approach to several other constructions. As a result, we improve the lower bound: First we show that the double zigzag chain with n points has Θ*n) non-crossing perfect matchings with λ≈3.0532. Next we analyze further generalizations of double zigzag chains: double r-chains. The best choice of parameters leads to a construction that has Θ*n) non-crossing perfect matchings with μ≈3.0930. The derivation of this bound requires an analysis of a coupled dynamic-programming recursion between two infinite vectors.

Moral: Don't count your boobies until they are hatched matched.

  pdf file
other papers about this subject
Last update: November 17, 2017.