تقرير
Connected Matchings
| العنوان: | Connected Matchings |
|---|---|
| المؤلفون: | Aichholzer, Oswin, Cabello, Sergio, Mészáros, Viola, Schnider, Patrick, Soukup, Jan |
| سنة النشر: | 2024 |
| المجموعة: | Computer Science Mathematics |
| مصطلحات موضوعية: | Computer Science - Computational Geometry, Mathematics - Combinatorics |
| الوصف: | We show that each set of $n\ge 2$ points in the plane in general position has a straight-line matching with at least $(5n+1)/27$ edges whose segments form a connected set, and such a matching can be computed in $O(n \log n)$ time. As an upper bound, we show that for some planar point sets in general position the largest matching whose segments form a connected set has $\lceil \frac{n-1}{3}\rceil$ edges. We also consider a colored version, where each edge of the matching should connect points with different colors. Comment: 20 pages, 14 figures; preliminary version in EuroCG 2024 |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2407.06131 |
| رقم الأكسشن: | edsarx.2407.06131 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |