Packing Plane Perfect Matchings into a Point Set

Abstract

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$? We prove that at least $\lceil {\log }_{2}n\rceil -2$ plane perfect matchings can be packed into any point set $P$. For some special configurations of point sets, we give the exact answer. We also consider some extensions of this problem.