My first post. This thread made me to register. There is some serious science going on here
Looks like your macro is running in O(n^2) or worse time complexity. You however, don't need to check every couple of caches. There is an algorithm that runs in O(n log n) time complexity. You just need to find Delaunay triangulation because is is dual problem to Voronoi and check only edges for maximum distance.
http://en.wikipedia.org/wiki/Delaunay_triangulation
http://en.wikipedia.org/wiki/Voronoi_diagram
or you can just take results from my webpage
http://mgs.cano.sk/proximity.php