Packing Plane Perfect Matchings into a Point Set
Ahmad Biniaz, Prosenjit K. Bose, Anil Maheshwari, Michiel Smid · Discrete Mathematics & Theoretical Computer Science · 2015
Given a set $P$ of $n$ points in the plane, where $n$ is even, we consider the following question: How many plane perfect matchings can be packed into $P$? For points in general position we prove the lower bound of ⌊log2$n$⌋$-1$. For some special configurations of point sets, we give the exact answer. We also consider some restricted variants of this problem.