The all-nearest-neighbors problem is to compute the nearest neighbor for each of the n input points; given the MST, it is readily solved in O(n) time, since the MST must include an edge linking each point to one of its nearest neighbors.