给定n个点（x，y坐标），我需要使用分而治之算法找到距离小于D的所有点对 .
最初我考虑使用类似的方法作为最近点问题，但是因为现在距离D是一个常数，所以我们可以在分裂区域中无限多个点而不是最近点问题中的第8个点 . 因此运行时间为O（n ^ 2），这并不比Brute-force好 .
任何想法或提示将不胜感激 .
在平均情况下提高效率的一种方法是首先使用相应的x对点的坐标（x，y）进行排序，并且如果使用典型的除法，则对应于y，如果相同的x（非常类似于字符串的排序） . 征服方法 .
然后从排序数组中的第一个点（我将其称为枢轴点）检查并知道距离D和枢轴点的x和y值，我们可以计算x值的上限 . 同样对于范围内的每个X，我们还可以计算其上下y范围，这会将问题的其余部分转换为嵌套范围迭代问题，该问题迭代直到超出范围（为了找到y迭代的起始位置，您可以需要对具有相同x）的数据集使用二进制搜索 .
例如，我们有一组点（1,0）（5,0）（3,1）（1,3）（3,4），我们需要找到它们之间距离的点对 . 首先对点进行排序，得到（1,0）（1,3）（3,1）（3,4）（5,0） . 设置（1,0）作为枢轴点，我们可以将x的上限计算为3，因此我们不必关心（5,0） . 然后我们可以检查x等于1的点集合并计算y的下限/上限-2和2，以便在x等于1的点集合中再次通过二分搜索定位较低的y . 在y之间具有y的点 - 2和2是有效点 . 重复上述步骤，然后我们终于可以找到所有有效的点对 .
1 回答
在平均情况下提高效率的一种方法是首先使用相应的x对点的坐标（x，y）进行排序，并且如果使用典型的除法，则对应于y，如果相同的x（非常类似于字符串的排序） . 征服方法 .
然后从排序数组中的第一个点（我将其称为枢轴点）检查并知道距离D和枢轴点的x和y值，我们可以计算x值的上限 . 同样对于范围内的每个X，我们还可以计算其上下y范围，这会将问题的其余部分转换为嵌套范围迭代问题，该问题迭代直到超出范围（为了找到y迭代的起始位置，您可以需要对具有相同x）的数据集使用二进制搜索 .
例如，我们有一组点（1,0）（5,0）（3,1）（1,3）（3,4），我们需要找到它们之间距离的点对 . 首先对点进行排序，得到（1,0）（1,3）（3,1）（3,4）（5,0） . 设置（1,0）作为枢轴点，我们可以将x的上限计算为3，因此我们不必关心（5,0） . 然后我们可以检查x等于1的点集合并计算y的下限/上限-2和2，以便在x等于1的点集合中再次通过二分搜索定位较低的y . 在y之间具有y的点 - 2和2是有效点 . 重复上述步骤，然后我们终于可以找到所有有效的点对 .