Capturing interactions between point sets with lunar minimum spanning trees

Consider a finite point set in a Euclidean space colored by 0, ..., s. We can capture aspects of the mutual interaction of the s+1 colors by studying the growing space of points covered by the r-thickening of each of the colors. In other words: for every (s+1)-tuple of points, one per each color, consider the intersection of the disks centered in those points with radius r. We call such a shape an s-lune of radius r, and we study the growing union of all s-lunes. The lunar minimum spanning tree (LMST) is the minimum spanning tree of a filtered connectivity graph of the lunes: with sublevel sets the 1-skeletons of the nerves of the growing lunes.

We show that the expected length of LMST—equivalently, the 1-norm of the 0-persistence of the growing lunes—for colored point sets randomly drawn from a unit square asymptotically behaves as the square root of the cardinality times a constant, generalizing a classical result for Euclidean minimum spanning trees.

I will focus on the context for the definition and the result–its relation to the standard Euclidean minimum spanning trees, persistent homology and chromatic topological data analysis. The proof of the result relies on a reformulation using Delaunay mosaics, highlighting how methods motivated by making computations efficient feed back into proving interesting theoretical results.