Lunar Generalizations of the Euclidean Minimum Spanning Tree in the Plane and their Expected Costs

Ondřej Draganov; Herbert Edelsbrunner; Sophie Rosenmeier; Morteza Saghafian

Source-linked AI summary

Lunar Generalizations of the Euclidean Minimum Spanning Tree in the Plane and their Expected Costs

Ondřej Draganov, Herbert Edelsbrunner, Sophie Rosenmeier, Morteza Saghafian

arXiv:2608.27118v1Aug 27, 2026cs.CGmath.ATmath.COmath.PR

TL;DR

The paper generalizes the Euclidean minimum spanning tree to colored points through unions of colored lunes and connects this construction to chromatic persistence. Using a geometric and probabilistic analysis, it proves that the expected lunar EMST cost grows as c_s√n, while the constants' precise values remain unknown.

Problem
The paper addresses how to generalize the EMST to s + 1 colored point sets and relate the resulting structure to chromatic persistence.
Method
The paper tracks component mergers in unions of disks or colored lunes as radius increases, using critical cells and Voronoi-overlay analysis to study the resulting lunar EMST.
Results
The expected lunar EMST cost is c_s√n in the limit as n goes to infinity, including settings with unequal color probabilities.
Takeaways & Limitations
The paper establishes existence of the asymptotic cost constant for each number of colors, extending the corresponding probabilistic theorem for the standard EMST.
Takeaways & Limitations
The precise values of c_s remain unknown, including c_0 for the standard EMST.

Abstract

from arXiv · show

Motivated by the recent introduction of chromatic persistent homology, we generalize the Euclidean minimum spanning tree (EMST) for $n$ points in $\mathbb{R}^2$ to the lunar EMST for the case in which the points come in $s+1$ colors. Calling the intersection of $s+1$ disks of radius $r$ centered at points with pairwise different colors a \emph{lune}, the generalized EMST reflects the history of the union of lunes as $r$ goes from $0$ to $\infty$, and its \emph{cost} is twice the difference between the radii when the arcs and nodes of the tree are formed. If the points are chosen uniformly at random in $[0,1]^2$ and colored randomly, the expected cost converges to some constant (that depends on $s$) times $\sqrt{n}$, as $n$ goes to infinity. The main contribution of this paper is a proof that this constant exists, however similar to the case of the classic EMST, its precise value remains elusive.

1. Introduction

The paper generalizes the EMST to points in s+1 colors using unions of s-lunes, linking the construction to chromatic persistence. For uniformly sampled, randomly colored points, it proves that expected lunar-EMST cost grows as a constant depending on s times √n.

Lunar EMST generalization: The s-lunar EMST generalizes the EMST by tracking connected components in unions of s-lunes as their radius increases.Each s-lune is formed from s+1 disks centered at points of pairwise different colors.
Connection to persistence: The construction connects lunar EMSTs to the degree-s relative persistence diagram of chromatic persistence.The cost is defined so that half the tree cost equals the 1-norm of the corresponding degree-0 persistence diagram.
Expected cost: For uniform points in the unit square with random (s+1)-coloring, the expected lunar-EMST cost converges to a constant depending on s times √n.This extends the established asymptotic form for the standard EMST.
Expected cost: For two colors, experiments estimate the constant between 0.350 and 0.352, compared with 0.646 to 0.648 for the standard EMST.These values are experimental suggestions rather than the paper’s existence proof.

2. Lunar Generalization of the EMST

The lunar EMST extends Kruskal’s geometric construction to differently colored points by tracking unions of intersecting disks, then reduces the resulting structure to critical cells and relates it to chromatic persistence.

Lunar EMST construction: The lunar EMST generalizes Kruskal’s EMST from disk unions to unions of s-lunes formed by s+1 differently colored points.For s=1, a lune is a convex lens; more generally, it is a convex region bounded by at most s+1 circular arcs.
Lunar EMST construction: The growth process is equivalently described by the sublevel sets of fmax, which takes the maximum across colors of the nearest-point distance.This function captures when points enter the union of colorful lunes as the radius increases.
Lunar Delaunay mosaic: The lunar Delaunay mosaic is dual to the overlay of the colored Voronoi tessellations, with cells representing domains, shared sides, crossings, and Voronoi vertices.The overlay bounds the number of domains by a quantity proportional to s^2n^2 under general position, while the dual mosaic provides the geometric construction.
Lunar Delaunay mosaic: The geometric lunar EMST runs Kruskal’s algorithm on the weighted 1-skeleton after Voronoi culling, preserving the same cost with a considerably smaller graph.Its nodes and arcs carry lunar radii, although these radii need not generally equal half the earlier combinatorial costs.
Critical and non-critical cells: Critical nodes, arcs, and triangles are precisely the cells associated with homotopy-changing events, and their total number is at most O(n).Criticality is characterized geometrically using empty smallest enclosing stacks and strict radius inequalities for incident cells.
Relation to chromatic persistence: The construction corresponds to chromatic persistence: colorful chromatic-alpha simplices biject with lunar-mosaic cells, preserving dimensions, radii, and boundaries.Consequently, the lunar EMST cost equals twice the 1-norm of the degree-s relative persistence diagram.

3. Poisson–Delaunay Mosaics

The paper develops Poisson-process bounds for Delaunay mosaics and their weighted, colored one-dimensional analogues, with particular attention to boundary effects. These estimates support analysis of lunar EMST formation and expected costs.

Expected sums of critical-edge and triangle radii are O(√n), while expected sums of squared radii are O(1).The bounds apply to critical simplices centered in [0,1]^2 whose smallest enclosing circles enclose at most one point.
Boundary-crossing critical edges and triangles have expected total radius O(1).This sharper bound concerns smallest enclosing circles centered in [0,1]^2 that cross the boundary.
Weighted Delaunay mosaics: Intersecting a planar Voronoi tessellation with a line yields a weighted one-dimensional Voronoi tessellation of orthogonal projections.Each projected point is weighted by its squared distance to the line, and growing one-dimensional balls sweep the resulting segments.
Weighted Delaunay mosaics: The expected sum of weighted radii of critical vertices, non-critical vertex-edge pairs, and critical edges centered in [0,1] is bounded by a constant.This is the one-dimensional weighted Poisson estimate used in the colored extension.
Weighted Delaunay mosaics: In the colored setting, the line intersection overlays s+1 weighted Voronoi tessellations into pieces, and fmax gives the radius at which lunes reach each point.The function takes the maximum nearest-point distance across colors.
Weighted Delaunay mosaics: The weighted lunar radius function assigns each piece and shared endpoint the minimum radius at which the union of lunes touches it.Critical vertices correspond to interior first contacts, while critical edges correspond to shared endpoints first touched in both adjacent pieces.

4. Main Theorem

The paper proves that randomly colored lunar EMSTs have an expected cost asymptotic to a constant depending on s times √n. The proof adapts Euclidean-functional methods and compares restricted, rooted, and unrestricted tree variants.

Proof strategy: The proof adapts a probabilistic method developed by Steele and Yukich to a cost function satisfying Euclidean-functional properties.These properties include normalization, homogeneity, translation invariance, and additional sub-additivity requirements.
Main result: The main theorem establishes a constant cs such that the expected cost of an s-lunar EMST on n uniformly sampled, randomly colored points is asymptotic to cs√n.The result applies for every fixed integer s ≥ 0.
Tree variants: Restricted lunar EMSTs are defined inside a compact region Q using the dual of the restricted overlay of colored Voronoi tessellations.The restricted tree minimizes cost within the restricted lunar Delaunay mosaic.
Random color probabilities: The same asymptotic form extends to independently colored points with fixed color probabilities, yielding a constant cp_s times √n.The proof also bounds anchor costs by O(1) and controls point-removal changes by a constant divided by √n.
Boundary control: The expected cost difference between unrestricted and restricted lunar EMSTs is bounded by a constant for a stationary Poisson process.This controls the boundary effects introduced by restricting the construction to the unit square.
Rooted comparison: Rooted lunar EMSTs represent the boundary of Q as a zero-cost root, with anchors added when restricted lunes first touch the boundary.Splitting arguments show that the cost increase is non-positive, supporting the required super-additivity comparison.

5. Discussion

The paper generalizes EMSTs to lunar trees and proves asymptotic expected-cost constants for random colored points, while leaving exact constants and several extensions open.

Discussion: For every non-negative integer s, a constant c_s exists such that random s-lunar EMST cost is c_s√n asymptotically.The points are uniform in [0,1]^2 and randomly (s + 1)-colored.
Discussion: The existence result extends to random colorings in which different colors have different probabilities.
Discussion: The precise value of c_s remains unknown, including c_0 for the standard EMST.For c_1, prior work provides bounds and computational estimates.
Discussion: Open questions include near-linear construction algorithms, relationships among constants, and asymptotic constants for higher homology degrees and dimensions.The overlay of color-specific Voronoi tessellations can be quadratic in n, while the topological tree has O(n) vertices.
Discussion: The proved setting is limited to the linear cost model, uniform sampling, and the unit square; higher dimensions, other cost models, and other distributions remain extensions.

Appendix A. Poisson–Delaunay Mosaics in Rd

The appendix frames the proof using stochastic geometry and establishes generalized tools for expected simplex counts and radius sums in Poisson–Delaunay mosaics.

Appendix A. Poisson–Delaunay Mosaics in R^d: The appendix generalizes a prior theorem and extends it to expected sums of radii and squared radii.It also treats weighted points and corresponding weighted-radius sums.
Appendix A. Poisson–Delaunay Mosaics in R^d: The stated theorem requires concepts and notation to specify how the paper’s result generalizes earlier work.

A.1. Generalizing Theorem 1 in [9].

This section derives expected counts of Poisson–Delaunay simplices under relaxed emptiness conditions, using spherical integral transformations and explicit probability factors.

A.1. Generalizing Theorem 1 in [9].: A Poisson–Delaunay mosaic assigns each simplex the radius of its smallest empty circumscribed sphere, yielding a generalized discrete Morse function.With probability 1, local finiteness and general position make the mosaic simplicial.
A.1. Generalizing Theorem 1 in [9].: The generalization counts simplices whose smallest circumscribed spheres contain j points in an η-fraction of their open balls, with 0 < η ≤ 1.This relaxes the requirement that the entire open ball be empty.
A.1. Generalizing Theorem 1 in [9].: Theorem A.1 gives an explicit expectation for these simplex counts as a function of η, j, dimension, intensity, and geometric constants.
A.1. Generalizing Theorem 1 in [9].: The geometric factor G^r_{m,ℓ} is defined through an integrated power of simplex volumes on a unit sphere, subject to facet-visibility conditions.
A.1. Generalizing Theorem 1 in [9].: The proof rewrites the Slivnyak–Mecke expectation through the spherical Blaschke–Petkantschin formula and integrates over geometric parameters and indicators.A change of variables reduces the resulting integral to the stated form.
A.1. Generalizing Theorem 1 in [9].: The theorem also yields bounds on expected sums of radii and squared radii, which are used later in the paper’s lemmas.

A.2. Radii and Squared Radii.

The appendix specializes the Poisson–Delaunay results to radius and squared-radius sums needed for the main proof, with incomplete gamma functions providing the explicit bounds.

A.2. Radii and Squared Radii.: Corollary A.2 bounds expected sums of radii and squared radii for simplices classified by dimension, facet visibility, η-fraction, and enclosed-point count.
A.2. Radii and Squared Radii.: The derivation rewrites the relevant integrals using the incomplete gamma function and repeats the argument with additional powers of the radius.
A.2. Radii and Squared Radii.: These results are restated in elementary forms for the three critical-edge and critical-triangle cases used in Lemmas 3.1 and 3.2.

A.3. Implications for Planar Case.

The planar appendix derives boundary-sensitive upper bounds for expected sums of radii and squared radii of critical edges and triangles in three cases.

A.3. Implications for Planar Case.: The three cases assume point configurations in R2 with either unrestricted locations or locations in [0,1]^2, with varying bounds on enclosing circles.Cases 1 and 2 require empty smallest enclosing circles, while Case 3 permits circles enclosing at most one point.
A.3. Implications for Planar Case.: The first four columns of Table 1 provide expectation bounds, while the last two address enclosing circles that are not fully contained in [0,1]^2.The boundary-restricted columns are handled separately from the general expectation bounds.
A.3. Implications for Planar Case.: Boundary contributions remain bounded independently of Poisson-process density for the three cases.The bound concerns expected sums of radii for critical edges and triangles whose enclosing circles are not fully inside the unit square.
A.3. Implications for Planar Case.: For any point set, each eligible pair contributes at most 2r^2 to the squared-radius comparison and exactly 2r^2 to its reference sum.The first inequality uses symmetry of the stationary Poisson process across vertical lines, and four sides of the square yield the final boundary factor.
A.3. Implications for Planar Case.: The appendix extends the planar analysis to weighted Voronoi tessellations and weighted Delaunay mosaics defined from points with real weights.The weighted radius function assigns each simplex the minimum radius at which its spheres reach a dual Voronoi cell.

A.4. Restating Theorem 1 in [8].

The appendix restates a theorem for weighted Delaunay mosaics over a k-plane in Rd, giving expected counts of bounded-radius intervals and identifying planar weighted-point density behavior.

A.4. Restating Theorem 1 in [8].: Theorem A.4 considers a stationary Poisson process of intensity ϱ>0, a k-plane in Rd, and a unit-volume Borel set Ω.It applies to intervals of type ℓ≤m with weighted radius at most r0 and centers in Ω.
A.4. Restating Theorem 1 in [8].: The theorem gives the expected number of intervals of type ℓ≤m whose weighted radius is at most r0 and whose center lies in Ω.The statement covers all 0≤ℓ≤m≤k and r0≥0.
A.4. Restating Theorem 1 in [8].: The expected density of non-redundant weighted points on R1 is √ϱ for a stationary Poisson process in R2.Most sampled points have Voronoi domains that do not intersect R1, and the resulting non-redundant locations are not necessarily a Poisson process on R1.

A.5. Weighted Radii and Squared Weighted Radii.

The appendix derives expected sums of weighted radii and squared weighted radii from the interval-count theorem and evaluates them for a planar process intersected by a line.

A.5. Weighted Radii and Squared Weighted Radii.: The appendix defines Fℓ≤m≤k≤d(r0) and Sℓ≤m≤k≤d(r0) as expected sums of weighted radii and squared weighted radii.These sums are derived from the interval-count formula in Theorem A.4.
A.5. Weighted Radii and Squared Weighted Radii.: Corollary A.5 gives the expected sums of weighted radii and squared weighted radii for intervals of type ℓ≤m with radius at most r0 and centers in a unit-volume set.The result holds for stationary Poisson processes in Rd and k-planes Rk.
A.5. Weighted Radii and Squared Weighted Radii.: The derivation repeats the interval-count argument with one and two additional powers of the radius inside incomplete gamma-function expressions.A substitution and simplification recover the two claimed relations.
A.5. Weighted Radii and Squared Weighted Radii.: For R1 embedded in R2, substituting the relevant parameters yields constant expectations for critical vertices, non-critical vertex-edge pairs, and critical edges in a unit-length interval.These three expectations are listed in Table 2.

Appendix B. Colorful Simplices of the Chromatic Delaunay Complex

Appendix B establishes a correspondence between colorful simplices and the lunar Delaunay mosaic, then uses chromatic genericity to analyze its filtration and critical events.

Appendix B. Colorful Simplices of the Chromatic Delaunay Complex: The lunar filtration maps each cell to the minimum fmax value over its dual overlay cell, so the cell appears when the first lune touches that cell.The overlay consists of intersections of Voronoi cells from the s+1 color classes.
Appendix B. Colorful Simplices of the Chromatic Delaunay Complex: For a colored point set in general position, colorful simplices of the chromatic Delaunay complex correspond bijectively to cells of the lunar Delaunay mosaic.The bijection preserves boundaries, shifts dimension by s, and matches the chromatic and lunar filtration values.
Appendix B. Colorful Simplices of the Chromatic Delaunay Complex: The correspondence preserves filtration values because both constructions use the minimum radius at which disks from all colors reach a common point in the overlay.Colorful facets correspond to facets in the lunar Delaunay mosaic.
Appendix B. Colorful Simplices of the Chromatic Delaunay Complex: A generalized discrete Morse filtration changes homotopy type only when a critical cell is added.The appendix applies this principle to the lunar Delaunay mosaic after establishing suitable genericity conditions.
Appendix B. Colorful Simplices of the Chromatic Delaunay Complex: Configurations violating the four strong chromatic genericity conditions form a zero-measure subset of the coordinate space.Violations of the later conditions are represented by zero sets of finitely many non-trivial rational functions.
Appendix B. Colorful Simplices of the Chromatic Delaunay Complex: Under strong chromatic genericity, removing a color represented by at least two vertices from a maximal colorful simplex strictly decreases its filtration radius.This property supports restricting the generalized discrete Morse structure to colorful simplices.

Appendix D. Results and Definitions

The appendix materials list generalized Poisson–Delaunay mosaic results and definitions concerning colorful simplices in the chromatic Delaunay complex.

The main text introduces the lunar EMST, critical-cell counting, chromatic-versus-lunar relationships, Poisson–Delaunay mosaics, and the main theorem.
Appendix A. Poisson–Delaunay Mosaics in R^d: Appendix A develops generalized Poisson–Delaunay mosaic results in R^d, including counting, measuring, boundary-crossing, and weighted results.
Appendix B. Colorful Simplices of the Chromatic Delaunay Complex: Appendix B studies colorful simplices of the chromatic Delaunay complex through chromatic-versus-lunar propositions and genericity and measure-zero lemmas.