空間を適当なサイズのメッシュで分割して、互いに近くにあるセルのペアに含まれる点だけで距離を計算すればいい
俺も全く同じことをやったことがあるんだが、見も蓋もないことを言えば
ぶっちゃけ手間暇かけてそういう工夫するよりCで普通に二重ループぶん回した方が結局手っ取り早くて遥かに速いよ