I would like to find the $m$ (where $m$ > 1) maximally distant subset of points from a collection of $n$ $d$-dimensional points.

This $m$ point subset will maximize some sort of distance metric (I am primarily interested in $L_2$-norm).  The dimension $d$ will likely be 3 - however if there was a way to define a distance metric that was meaningful in $SE(3)$ (Special-Euclidean Group Lie Algebra) that would be favorable (the points in my motivating example are 6-Degrees of Freedom locations in 3-$D$ space i.e. 3 - position + 3 - orientation).  Having said this any solution that works just in cartesian 3-space will also be fine.

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?  Even if there is away to solve the QP in reasonable time with very large $n$ that would be great.