The paper was only an algorithm for part of this — I can't remember the paper, but it gave an algorithm to find all of the closest points to a line.

How my algorithm worked was to break the search space into a 2D array of much smaller squares. In the initialisation phase I put the points in each square that are closest to any search point in that square (some points were in multiple squares). Therefore, when a search was run, the square the search point falls in is looked up, and the list of twenty or so points was looked through for the closest point in a slightly optimised way (no square roots here).

Sounds like an R* tree or some variant of that?