Discrete Mathematics & Theoretical Computer Science, Vol 17, No 2 (2015)

Font Size:  Small  Medium  Large

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