pith. sign in

arxiv: 1502.05332 · v1 · pith:JQDOQAFEnew · submitted 2015-02-18 · 💻 cs.CG

The number of non-crossing perfect plane matchings is minimized (almost) only by point sets in convex position

classification 💻 cs.CG
keywords numberpointspositionconvexmatchingsnon-crossingonlyperfect
0
0 comments X
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.