# Algorithm to project onto line segments

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?

• Any reason you couldn't just throw it in a quad tree? (Treat each line as a continuous set of points, stop iterating when any quad has points from only a single line segment.) – Veedrac Jul 25 '17 at 15:47
• You might also want to search around for "voronoi diagram line segments", though I don't know whether the solutions there will match your use-case. – Veedrac Jul 25 '17 at 15:54
• I'm wondering if there are data structures for 2D visibility that be useful here. Or perhaps you can adapt a sweepline algorithm for constructing a Voronoi diagram to handle the case of line segments rather than points. – D.W. Jul 25 '17 at 16:02
• Thanks for the ideas. I'll have a search for quad trees (I had this vague idea they only helped with nearest neighbour like searches; but I'm probably mistaken) and will have another look at voronoi diagrams. – Matthew Daws Jul 25 '17 at 19:40
• CGAL can compute voronoi diagrams for line segments: doc.cgal.org/Manual/3.1/doc_html/cgal_manual/… – adrianN Jul 26 '17 at 7:57