When a pathologist examines a biopsy under magnification, one of the first questions she asks is spatial: are the tumor cells clustered apart from the immune cells, or are they interleaved? The answer is not merely visual. It is predictive. Spatial intermingling between cell populations correlates with treatment response, disease progression, and survival. The ability to *measure* that intermingling—rigorously, scalably, and without dependence on local density assumptions—is an open problem of significant biological and computational consequence.
A recent paper by Todor Antić, Morteza Saghafian, Maria Saumell, Felix Schröder, Josef Tkadlec, and Pavel Valtr approaches this problem from an unexpected direction: discrete geometry. Their paper, *How Many Times Can Two Minimum Spanning Trees Cross?*, investigates the topological interaction between the connectivity structures of two spatially distributed point sets, and in doing so provides a rigorous mathematical foundation for a new family of spatial mixedness metrics.
The Crossing Number as a Mixing Measure
For any two-colored point cloud—say, red cells and blue cells—one can construct a minimum spanning tree for each color group independently. The degree to which these two trees spatially interleave, measured by counting how many times their edges cross each other in the plane, provides a natural geometric proxy for mixedness. When the populations are segregated, their trees tend to occupy distinct regions, crossing rarely. When they are thoroughly interspersed, the trees necessarily traverse each other's territory, crossing frequently.
The appeal of this measure is that it captures *global* connectivity, not just local density. A nearest-neighbor statistic describes the immediate neighborhood of each point; the MST crossing number describes how a population spans the space it occupies, and whether that span is topologically entangled with the span of another population.
"The crossing of minimum spanning trees serves as a natural geometric proxy for mixedness, capturing the extent to which two or more point sets are spatially intermingled—not just locally, but across the full reach of each population's connectivity structure."
The central theoretical result of the paper is that for any generic set of $n$ points with any two-coloring, the maximum number of crossings between the two MSTs grows linearly with $n$. This is a crucial guarantee: it means the metric is not only mathematically well-defined but practically computable at scale. Linear growth implies that as datasets grow from hundreds to millions of points, the crossing number remains a tractable quantity to evaluate.
Configurations, Convexity, and Randomness
The paper moves carefully through the space of possible configurations. For points in convex position, the authors prove a lower bound of approximately $n/2$ crossings in the most adversarial coloring—and then demonstrate, through a series of elegant grid perturbations, that even convex configurations can be pushed to approximately $5n/8$ crossings. The geometry of the point set's distribution, it turns out, affects its capacity for topological entanglement in subtle and non-obvious ways.
Perhaps most relevant for applied researchers is the stochastic result: for points drawn uniformly at random from a unit square and colored randomly, the expected crossing number is also linear in $n$. This confirms that the measure is not a curiosity of geometric extremes but a well-behaved, predictable property of the kinds of noisy, unstructured data that appear in biological imaging, urban spatial analysis, and multi-agent simulation.
The authors acknowledge that the precise constant governing the linear lower bound remains an open problem, and the extension of the framework to higher dimensions and non-Euclidean geometries is active territory. But in establishing linear growth as a fundamental property of MST crossing across generic, random, and convex configurations, Antić and colleagues have given spatial analysts something valuable: a measure of mixedness that respects global topology, scales gracefully, and comes with rigorous combinatorial guarantees.