Bichromatic Perfect Matchings with Crossings

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 \(\frac{3n^2}{8}-\frac{n}{2}+c\) crossings, for some \( -\frac{1}{2} \leq c \leq...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2023-09
Main Authors: Oswin Aichholzer, Felsner, Stefan, Rosna, Paul, Scheucher, Manfred, Vogtenhuber, Birgit
Format: Article
Language:English
Subjects:
Matching
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 \(\frac{3n^2}{8}-\frac{n}{2}+c\) crossings, for some \( -\frac{1}{2} \leq c \leq \frac{1}{8}\). This bound is tight since for any \(k> \frac{3n^2}{8} -\frac{n}{2}+\frac{1}{8}\) there exist bichromatic point sets that do not admit any perfect matching with \(k\) crossings.
ISSN:2331-8422