The irony is that his solution has an unnecessary log(n) term, because it's finding each point independently instead of taking advantage of the fact that the in

The irony is that his solution has an unnecessary log(n) term, because it's finding each point independently instead of taking advantage of the fact that the input points are also a dense grid. ;) so it can probably run 2-10x faster than the optimized version, assuming that the function call to bin search is probably a lot more expensive than filling in the grid, which R can do internally. (You don't have to binary search each time, you have a known starting point from the previous point. So you binary search once to find the top-left point and the rest is just checking if you moved into the next global grid cell.)