## 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].
### Abstract

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.0438^{n})
and
Ω^{*}(3^{n}), 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
Θ(3^{n}/`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.

Last update: November 17, 2017.