An alternative solution that I discovered a year ago. My problem was that I had a list of 2D points lying in an image. I wanted to calculate the distance to the nearest point for every pixel - somewhat similar to a Voronoi diagram except I needed the distances as well as the cells.

When I asked Stackoverflow, having tried Kdtree, someone suggested a simple brute force solution in OpenCL (using the pyopencl library):

https://stackoverflow.com/questions/24020409/producing-a-nea...

Scipy's KDtree took around 30 seconds per 1MP image. The OpenCL solution took 50ms (at the expense of my screen locking up)!

As the response said: "And the improvement was quite good.", no kidding.