Connected Matchings
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866929728253853696 |
|---|---|
| author | Aichholzer, Oswin Cabello, Sergio Mészáros, Viola Schnider, Patrick Soukup, Jan |
| author_facet | Aichholzer, Oswin Cabello, Sergio Mészáros, Viola Schnider, Patrick Soukup, Jan |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_06131 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Connected Matchings Aichholzer, Oswin Cabello, Sergio Mészáros, Viola Schnider, Patrick Soukup, Jan Computational Geometry 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. |
| title | Connected Matchings |
| topic | Computational Geometry Combinatorics |
| url | https://arxiv.org/abs/2407.06131 |