I have the following problem: A large number $N$ of (finite length) line segments in the plane (if it helps, we can assume non-intersecting except at end points, and forming a graph with a small number of components); and a smaller number $n$ of points. For each point, I wish to find the closest line segment.
Given one line segment, this is easy: orthogonally project onto the line, and if this doesn't fall on the line segment, choose the appropriate end point. This gives a naive $O(Nn)$ algorithm.
I am wondering if there is a clever data structure which, with some pre-processing on the lines, would give a faster algorithm?