Efficient Geometric Clustering via t-Spanners and Local Adaptive MST Edge Cutting

Clustering a set of points in the Euclidean plane is a fundamental problem in computational geometry and data analysis, with

applications spanning image segmentation, spatial data mining, and pattern recognition. Minimum Spanning Tree (MST)-

based clustering methods offer a geometrically intuitive approach, but suffer from the O(n2 ) cost of constructing the complete

Euclidean graph for large point sets. We propose an efficient O(n log n) algorithm for clustering n points in the Euclidean

plane. Our method constructs a t-spanner with stretch factor t = 1 + ε for any user-chosen ε > 0 via a Well-Separated Pair

Decomposition (WSPD), yielding a sparse graph of O(n/ε2 ) edges whose MST approximates the true Euclidean MST within a

factor of 1 + ε. For any fixed ε > 0 this is O(n) edges, though the constant grows as ε → 0. Clustering is then performed by a

novel local adaptive edge-cutting criterion: an edge (ai , bi ) is removed if its weight exceeds α times λi = max(δ(ai ), δ(bi )),

where δ(p) is the local scale at p (approximated in practice by its k-nearest-neighbour distance). This makes the criterion scale-

aware and sensitive to local point density. When δ(p) is taken as the FST leaf cell diameter, all quantities needed for cutting

are available as byproducts of the Fair Split Tree construction at no extra asymptotic cost. Experiments on synthetic Gaussian

datasets and standard 2D clustering benchmarks (R15, Aggregation) confirm that the method achieves perfect clustering on well-

separated point sets and competitive NMI on denser configurations.