K-d trees are even built in to SciPy, which the author probably already has installed (Scikit-Learn also has an implementation).
Sure, absolutely. Just wanted to point out that the article isn't very sophisticated.
It is simple indeed. The performance I got was good enough to spare me the effort of using quad trees. Yes, I know what quad trees are. I even coded octrees for 3D reasoning in a previous life ;)