I would like to find the m maximally distant subset of points from a collection of n d-dimensional points.

Note: I found a similar question on this topic, but unfortunately the proposed answer requires convex optimization (QP) which is not suitable for the very large number of points that I require (n).

http://stackoverflow.com/questions/5400905/most-mutually-distant-k-elements-clustering

I have tried the following algorithm

Add the n d-dimensional points to a kd-tree while subset S size is greater than n find the point q from the kd-tree that is least distant to any of its neighbors remove point q from the kd-tree and the subset S return the subset S of m maximally distant points

This is obviously non-deterministic since the order in which the points are removed affects the eventual subset of S (this however occasionally returns the correct solution). But the complexity is (n - m)log(n) which is favorable considering n will be > 100,000.

Does anyone have ideas about how to improve/replace the above algorithms whilst keeping the complexity down?