The number of non-crossing perfect plane matchings is minimized (almost) only by point sets in convex position
classification
💻 cs.CG
keywords
numberpointspositionconvexmatchingsnon-crossingonlyperfect
read the original abstract
It is well-known that the number of non-crossing perfect matchings of $2k$ points in convex position in the plane is $C_k$, the $k$th Catalan number. Garc\'ia, Noy, and Tejel proved in 2000 that for any set of $2k$ points in general position, the number of such matchings is at least $C_k$. We show that the equality holds only for sets of points in convex position, and for one exceptional configuration of $6$ points.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.