I don't remember the algorithm exactly and Google isn't yielding any useful results, but I seem to recall that if all the distances are integers (or if you make all the distances integers via scaling/rounding) there is a much faster algorithm that relies on "stepping upward" and considering increasingly larger distances. All I remember is that it's very similar to the same principle that makes radix sort sub-linearithmic.

Anyone know what I'm talking about?