Find all line segment pairs with distance less than a certain bound

Question

Let L1,...,Ln be n different line segments in the plane (IR^2). They shall be pairwise non-intersecting. Furthermore let r signify a distance (a real value). Consider the problem of finding all pairs (i,j) where the (euclidean) distance of Li and Lj is less than r.

I wrote a simple and straightforward sweep-line algorithm for the problem which is about of runtime O(n^(3/2)), if one can assume that for all relevant x0 coordinates about n^(1/2) line segments lie in the vertical stripe bounded by x = x0 and x = x0 + r.

Of course I was curious, if there is a well-known (or not so well-known) better algorithm (hopefully a O(n log(n)) algorithm or such), but could not find anything appropriate via google or more specifically stackoverflow.

Does someone know more?

Answer 1

If you replace the segments by rectangles corresponding to a dilation by r/2, the rectangle outlines will intersect when the segments are closer than r. (In fact, there will be a fraction of false positives, because the corners should be rounded. But the false positives can be rejected after the fact.)

So you could use the standard Bentley-Ottman to perform your task, with no degradation of the asymptotic complexity. (Note that two rectangle outlines can intersect up to eight times, but only in extreme situations.)

https://en.wikipedia.org/wiki/Bentley–Ottmann_algorithm