2015/01/15 by Biniaz, Ahmad, Bose, Prosenjit, Maheshwari, Anil +1 · 1 citation
#Computational Geometry (cs.CG) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1501.03686
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 \lceillog2n\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.