Packing Plane Perfect Matchings into a Point Set
Ahmad Biniaz, Prosenjit Bose, Anil Maheshwari, Michiel Smid
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? For
points in general position we prove the lower bound of
⌊log2n⌋-1. For some special
configurations of point sets, we give the exact answer. We also
consider some restricted variants of this problem.
Full Text: PDF