Bichromatic Perfect Matchings with Crossings

09/01/2023
by   Oswin Aichholzer, et al.
0

We consider bichromatic point sets with n red and n blue points and study straight-line bichromatic perfect matchings on them. We show that every such point set in convex position admits a matching with at least 3n^2/8-n/2+c crossings, for some -1/2≤ c ≤1/8. This bound is tight since for any k> 3n^2/8 -n/2+1/8 there exist bichromatic point sets that do not admit any perfect matching with k crossings.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset