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

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-nearest-neighbour-distance-map-for-a-set-of-points 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.