Euclidean Maximum Matchings in the Plane---Local to Global
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910464713162752 |
|---|---|
| author | Biniaz, Ahmad Maheshwari, Anil Smid, Michiel |
| author_facet | Biniaz, Ahmad Maheshwari, Anil Smid, Michiel |
| contents | Let $M$ be a perfect matching on a set of points in the plane where every edge is a line segment between two points. We say that $M$ is globally maximum if it is a maximum-length matching on all points. We say that $M$ is $k$-local maximum if for any subset $M'=\{a_1b_1,\dots,a_kb_k\}$ of $k$ edges of $M$ it holds that $M'$ is a maximum-length matching on points $\{a_1,b_1,\dots,a_k,b_k\}$. We show that local maximum matchings are good approximations of global ones.
Let $μ_k$ be the infimum ratio of the length of any $k$-local maximum matching to the length of any global maximum matching, over all finite point sets in the Euclidean plane. It is known that $μ_k\geqslant \frac{k-1}{k}$ for any $k\geqslant 2$. We show the following improved bounds for $k\in\{2,3\}$: $\sqrt{3/7}\leqslantμ_2< 0.93 $ and $\sqrt{3}/2\leqslantμ_3< 0.98$. We also show that every pairwise crossing matching is unique and it is globally maximum.
Towards our proof of the lower bound for $μ_2$ we show the following result which is of independent interest: If we increase the radii of pairwise intersecting disks by factor $2/\sqrt{3}$, then the resulting disks have a common intersection. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_20424 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Euclidean Maximum Matchings in the Plane---Local to Global Biniaz, Ahmad Maheshwari, Anil Smid, Michiel Computational Geometry Discrete Mathematics Let $M$ be a perfect matching on a set of points in the plane where every edge is a line segment between two points. We say that $M$ is globally maximum if it is a maximum-length matching on all points. We say that $M$ is $k$-local maximum if for any subset $M'=\{a_1b_1,\dots,a_kb_k\}$ of $k$ edges of $M$ it holds that $M'$ is a maximum-length matching on points $\{a_1,b_1,\dots,a_k,b_k\}$. We show that local maximum matchings are good approximations of global ones. Let $μ_k$ be the infimum ratio of the length of any $k$-local maximum matching to the length of any global maximum matching, over all finite point sets in the Euclidean plane. It is known that $μ_k\geqslant \frac{k-1}{k}$ for any $k\geqslant 2$. We show the following improved bounds for $k\in\{2,3\}$: $\sqrt{3/7}\leqslantμ_2< 0.93 $ and $\sqrt{3}/2\leqslantμ_3< 0.98$. We also show that every pairwise crossing matching is unique and it is globally maximum. Towards our proof of the lower bound for $μ_2$ we show the following result which is of independent interest: If we increase the radii of pairwise intersecting disks by factor $2/\sqrt{3}$, then the resulting disks have a common intersection. |
| title | Euclidean Maximum Matchings in the Plane---Local to Global |
| topic | Computational Geometry Discrete Mathematics |
| url | https://arxiv.org/abs/2405.20424 |