Yeah I'm aware of this guy. He is not the worlds most brilliant algorithms designer, ive had a chance to speak with him. For example in the example:
he was using a algorithm that was O(n*log(n)) but he could have used a bucket sort for a O(n) because he was under the false assumption that this is the best one can do, which is abviously false (lucky for us or youd never get mail). He equated the statement that the fastest comparasion sort is n*log(n) but there are sorts that are based on noncomparasion.
Anwyay the KD tree is fast for random lookup of nearest neigbourhood like raytracing for instance. However since your going to test each particle against each particle ANYWAY, you can do this much faster with with a carefully selected insertion sort and some bucketisation. Ive tested this and its about 1.2-2 times faster for most data. AND its way easier to implement.
Why? Well because you need to go up and down in the kd tree. to find the nearest neighbour. This takes time IF the bucket happens to split where the neigbour is. A KD tree is fabulous when the data doesnt need to be all mined or the lookup is random like in raytracing however.
So inside one bucket the insertion sort is n*log*n + a worst case of n*n.
wheras the kd tree is n*log*n + works cas eof n*n + a additional b*n*n.
Since a tensional search is never going to go into the worst case scenario insertion sort wins on most random data. However it may in some ordered data be VERY bad indeed which is why you introduce bucketing. In the primary and secondary directions. THis way you allways have minimal amount of inter bucket comparasion need. Tryue granted the kd tree is againg slightly better in worst case scenario, but simple sort beats most situations better.
Now algorithmically they both produce the same kind of lookup. They are jsut organized differently with the sort method designed for this purpose alone. The kd tree optimizes buildup, while i optimize the organisation for searching systematically, which is what yiu want to do.
Anyway that code needs a lot of whacking to get it working so its not optimal. I just pointed out thet there are easier methods. Since youd need to change the code much anyway.