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?

  • 1
    $\begingroup$ 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.) $\endgroup$ – Veedrac Jul 25 '17 at 15:47
  • 1
    $\begingroup$ 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. $\endgroup$ – Veedrac Jul 25 '17 at 15:54
  • $\begingroup$ 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. $\endgroup$ – D.W. Jul 25 '17 at 16:02
  • $\begingroup$ 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. $\endgroup$ – Matthew Daws Jul 25 '17 at 19:40
  • $\begingroup$ CGAL can compute voronoi diagrams for line segments: doc.cgal.org/Manual/3.1/doc_html/cgal_manual/… $\endgroup$ – adrianN Jul 26 '17 at 7:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.