How many times can two minimum spanning trees cross?
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2601.20060
curl -X POST /api/v1/records/arxiv/2601.20060/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2601.20060/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'