تقرير
Bichromatic Perfect Matchings with Crossings
العنوان: | Bichromatic Perfect Matchings with Crossings |
---|---|
المؤلفون: | Aichholzer, Oswin, Felsner, Stefan, Paul, Rosna, Scheucher, Manfred, Vogtenhuber, Birgit |
سنة النشر: | 2023 |
المجموعة: | Computer Science Mathematics |
مصطلحات موضوعية: | Computer Science - Computational Geometry, Mathematics - Combinatorics |
الوصف: | 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. Comment: Appears in the Proceedings of the 31st International Symposium on Graph Drawing and Network Visualization (GD 2023) |
نوع الوثيقة: | Working Paper |
URL الوصول: | http://arxiv.org/abs/2309.00546 |
رقم الأكسشن: | edsarx.2309.00546 |
قاعدة البيانات: | arXiv |
الوصف غير متاح. |