Download Geometric Minimum Spanning Trees with Filter-Kruskal

Computing the geometric minimum spanning tree (GMST)is a classic computational geometry problem which arises in many applications including clustering and pattern classication [34], surface reconstruction [25], cosmology [4, 6], TSP approximations [2] and computer graphics [23]. Given a set of n points P in Rd, the GMST of P is dened as the minimum weight spanning tree of the complete undirected weighted graph of P, with edges weighted by the distance between their end points. In this paper, we present a practical deterministic algorithm to solve this problem eciently, and in a manner that easily lends itself to parallelization.