Delaunay observation
Every MST edge is a Delaunay edge. Compute Delaunay (O(N log N)) → run MST on it (O(N log N) edges).
Advertisement
Delaunay properties
N points → O(N) Delaunay edges. Contains MST. Contains nearest-neighbor edges.
Advertisement
Alternative: k-d tree
Well-separated pair decomposition (WSPD). O(N log N) construction, spanner.
Applications
Network topology design. Cluster analysis. Facility placement.