تقرير
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 |
| الوصف غير متاح. |