Performance of find methods, comparison with linear search

[John Femiani]

Sylvain said:
> 
> I find your tests awesome. I am totally gonna use it :-) I am just
> gonna replace the linear search by ANN, in order to compare to
> something better. Well, I hope I'll be able to do that soon.
> 
> Thanks a lot for the code. Octave looks like a great tool.
> 

BTW: octave works great on windows too. I was able to run the tests and
generate plots on my windows workstation no prob. -- well, actually only
a minor problem of a missing header file in the cpp file.

I suspect ANN will be a lot better because kdtree is not the best
performing structure for range queries. There are O(log n + k) methods
using orthogonal range trees and fractional cascading. I think kdtree is
O(sqrt(n) + k), where k is the number of matches and n is the total
number of points.

I think there is also a range query structure in CGAL but it has a funky
QPL license.  

Does libkdtree have a homepage? If so, it would be nice to show these
plots there I think.

-- John