How many times can two minimum spanning trees cross?
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917226937843712 |
|---|---|
| author | Antić, Todor Saghafian, Morteza Saumell, Maria Schröder, Felix Tkadlec, Josef Valtr, Pavel |
| author_facet | Antić, Todor Saghafian, Morteza Saumell, Maria Schröder, Felix Tkadlec, Josef Valtr, Pavel |
| contents | Let $P$ be a generic set of $n$ points in the plane, and let $P=R\cup B$ be a coloring of $P$ in two colors. We are interested in the number of crossings between the minimum spanning trees (MSTs) of $R$ and $B$, denoted by $\crossAB(R,B)$. We define the \emph{bicolored MST crossing number} of $P$, denoted by $\cross(P)$, as $\cross(P) = \max_{P= R\cup B}(\crossAB(R,B))$. We prove a linear upper bound for $\cross(P)$ when $P$ is generic. If $P$ is dense or in convex position, we provide linear lower bounds. Lastly, if $P$ is chosen uniformly at random from the unit square and is colored uniformly at random, we prove that the expected value of $\crossAB(R,B)$ is linear. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_20060 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | How many times can two minimum spanning trees cross? Antić, Todor Saghafian, Morteza Saumell, Maria Schröder, Felix Tkadlec, Josef Valtr, Pavel Computational Geometry Combinatorics Let $P$ be a generic set of $n$ points in the plane, and let $P=R\cup B$ be a coloring of $P$ in two colors. We are interested in the number of crossings between the minimum spanning trees (MSTs) of $R$ and $B$, denoted by $\crossAB(R,B)$. We define the \emph{bicolored MST crossing number} of $P$, denoted by $\cross(P)$, as $\cross(P) = \max_{P= R\cup B}(\crossAB(R,B))$. We prove a linear upper bound for $\cross(P)$ when $P$ is generic. If $P$ is dense or in convex position, we provide linear lower bounds. Lastly, if $P$ is chosen uniformly at random from the unit square and is colored uniformly at random, we prove that the expected value of $\crossAB(R,B)$ is linear. |
| title | How many times can two minimum spanning trees cross? |
| topic | Computational Geometry Combinatorics |
| url | https://arxiv.org/abs/2601.20060 |