令 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)) 算法等），但无法通过谷歌或更具体地说找不到任何合适的算法堆栈溢出。
有人知道更多吗？
