Query all pair of points whose distance is smaller than a threshhold
<p>The problem is simple, just like the query_pair method in python scipy <a href="http://docs.scipy.org/doc/scipy-0.14.0/reference/generated/scipy.spatial.KDTree.html" rel="nofollow">kdtree implmentation</a>.</p>

<p>I want a c/c++ version of that. However, I find typically a kd-tree implementation only offer API of NN, k-NN, Range query.</p>

<p>I try to implement query_pair in c++ by using range query as the building blocks. However, in this way, I have to filter the result since each pair of point will be found twice. The performance is not good enough.</p>

<p>I want to know two thing:</p>

<ol>
<li>is there any way specifically for efficient point pair query? even an approximate one is enough.</li>
<li>in some paper 'Reduced hair models', it said that k-NN is more efficient than fixed range search because of more efficient pruning. Why?</li>
</ol>