查找距离小于某个界限的所有线段对

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

设L1,...,Ln为平面(IR^2)中n条不同的线段。它们应成对不相交。此外，令 r 表示距离（实数值）。考虑找到所有对 (i,j) 的问题，其中 Li 和 Lj 的（欧氏）距离小于 r。

我写了一个简单明了的扫线算法来解决运行时间 O(n^(3/2)) 的问题，如果可以假设所有相关的 x0 坐标都是关于 n^(1/ 2) 线段位于以 x = x0 和 x = x0 + r.

为界的垂直条纹中

当然我很好奇，如果有一个众所周知的（或不太知名的）更好的算法（希望是 O(n log(n)) 算法之类的），但找不到合适的通过 google 或更具体地说是 Whosebug。

有人知道更多吗？

如果用对应于 r/2 膨胀的矩形替换线段，当线段比 r 更近时，矩形轮廓将相交。（其实会有一小部分误报，因为角应该是圆的。但是误报可以事后拒绝。）

所以您可以使用标准的 Bentley-Ottman 来执行您的任务，而不会降低渐近复杂性。（请注意，两个矩形轮廓最多可以相交八次，但仅限于极端情况。）