The Euclidean MST-ratio for Bi-colored Lattices
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_ | 1866910671812165632 |
|---|---|
| author | di Montesano, Sebastiano Cultrera Draganov, Ondřej Edelsbrunner, Herbert Saghafian, Morteza |
| author_facet | di Montesano, Sebastiano Cultrera Draganov, Ondřej Edelsbrunner, Herbert Saghafian, Morteza |
| contents | Given a finite set, $A \subseteq \mathbb{R}^2$, and a subset, $B \subseteq A$, the \emph{MST-ratio} is the combined length of the minimum spanning trees of $B$ and $A \setminus B$ divided by the length of the minimum spanning tree of $A$.
The question of the supremum, over all sets $A$, of the maximum, over all subsets $B$, is related to the Steiner ratio, and we prove this sup-max is between $2.154$ and $2.427$.
Restricting ourselves to $2$-dimensional lattices, we prove that the sup-max is $2.0$, while the inf-max is $1.25$.
By some margin the most difficult of these results is the upper bound for the inf-max, which we prove by showing that the hexagonal lattice cannot have MST-ratio larger than $1.25$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_10204 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | The Euclidean MST-ratio for Bi-colored Lattices di Montesano, Sebastiano Cultrera Draganov, Ondřej Edelsbrunner, Herbert Saghafian, Morteza Computational Geometry Combinatorics 52C05, 05C10 G.2 Given a finite set, $A \subseteq \mathbb{R}^2$, and a subset, $B \subseteq A$, the \emph{MST-ratio} is the combined length of the minimum spanning trees of $B$ and $A \setminus B$ divided by the length of the minimum spanning tree of $A$. The question of the supremum, over all sets $A$, of the maximum, over all subsets $B$, is related to the Steiner ratio, and we prove this sup-max is between $2.154$ and $2.427$. Restricting ourselves to $2$-dimensional lattices, we prove that the sup-max is $2.0$, while the inf-max is $1.25$. By some margin the most difficult of these results is the upper bound for the inf-max, which we prove by showing that the hexagonal lattice cannot have MST-ratio larger than $1.25$. |
| title | The Euclidean MST-ratio for Bi-colored Lattices |
| topic | Computational Geometry Combinatorics 52C05, 05C10 G.2 |
| url | https://arxiv.org/abs/2403.10204 |