@ManfredWeis any suggestions would be welcome. Thanks!

@ManfredWeis I have just found a better reference for solving Binary Quadratic Programming problems "Solving Large Scale Binary Quadratic Problems:Spectral Methods vs. Semidefinite Programming" It seems that O(n^3) solutions exist (Eigenvalues) that fits nicely with large n and can be easily implemented with a standard linear algebra package. So I think I will pursue that solution.

Thanks @JosephO'Rourke I thought this too, but consider a set of $n$ > $3$ points on a line where you are seeking the $n$ > $m$ >= $3$ subset that are maximally distant.

Hi @HughThomas, thanks for replying. Here is a link to the kd-tree (en.wikipedia.org/wiki/K-d_tree)

I have amended the question to reflect you comments - thanks!

@JosephO'Rourke thanks for amending the tag - I am new on this forum and was influenced by existing implementation which is using the kd-tree

@GerryMyerson to clarify your question - you are right m > 1