我可以计算距离严格小于增量的最近分割点对吗
Can I compute closest split pair of points where distance is strictly less than delta
The Closest Pair of Points Problem 最近让我着迷。更具体地说，分而治之算法。
这个递归算法要求我将一组点分成两个块，a 和 b 并为每个块计算最接近的点对，然后计算它们之间最近的点对块和 return 这 3 个数量中的最小值。
计算块之间最近点的算法仅通过迭代最多 7 个点来工作，这些点最多 min(a, b) 远离 a 中的最后一个点（中位数元素整套）。
这两张图更能说明问题。 min(a, b) = Delta.
我知道如果我在 l 线上的两边都有 2 个点，a 和 b，我最多需要比较 7 个点中间条。
不过我想知道的是，如果我构造中间条带的点数严格小于距 l 的 Delta，难道我不能只比较接下来的 4 个点，而不是 7 个，因为我可以只适合 l 的每一侧 2 个点，小于 Delta 远离 l 和 Delta 彼此远离？
编辑：
我也在 cs stackexchange 上开始悬赏一个非常相似的问题，我们在那里进行了非常有趣的讨论。所以我将其链接 here. We've also started a very insightful chat here.
注意：根据与@Danilo Souza Morães 和@burnabyRails 的广泛讨论，此答案已更新以供将来参考，@burnabyRails 是 Danilo 提到的 accepted answer on a similar question by Danilo on the CS site. The main problem with the original answer is that I assumed that a bit different algorithm is used/discussed here. Since the original answer provided some important insights to Danilo it is preserved as is at the end. Also if you are going to read the discussion 的作者在他的回答中，请务必先阅读此处的介绍，以更好地理解我的意思。添加的前言讨论了所讨论算法的不同版本。
简介
该算法基于两个主要思想：
- 典型的递归分治法
- 事实上，如果您已经知道左右区域的最佳距离，您可以在
O(N) 时间内执行 "combine" 步骤，因为您可以证明您可以对每个区域进行检查O(1) 时间点。
尽管如此，在实践中有多种方法可以实现相同的基本想法，尤其是组合步骤。主要区别是：
- 您是否以不同的方式独立对待 "left" 和 "right" 点？
- 对于每个点，你是做固定数量的检查，还是先过滤候选项，然后只对过滤后的候选项进行距离检查？请注意，您可以在不中断
O(N*log(N)) 时间的情况下进行一些过滤，前提是您可以确保以分摊 O(1) 的方式完成过滤。换句话说，如果你知道优秀候选人的数量有一个很大的上限，你就不必检查确切的候选人数量。
CLRS Introduction to Algorithms 中算法的经典描述清楚地回答了问题 #1，因为您混合了 "left" 和 "right" 点并共同处理它们。至于#2，答案不太清楚（对我来说），但它可能意味着检查一些固定数量的点。这似乎是 Danilo 想问的问题的版本。
我想到的算法在这两点上都是不同的：它通过 "left" 点上升，并根据所有筛选的 "right" 候选者检查它们。显然，我在写答案时和最初的聊天讨论中并没有意识到这种差异。
"My"算法
这是我想到的算法的草图。
开始步骤很常见：我们已经处理了 "left" 和 "right" 点并且知道最好的 </code> 到目前为止，我们让它们沿 <code>Y 轴排序。我们还过滤掉了所有不在 ± 条带中的点。
外层循环是我们向上遍历"left"点。现在假设我们处理一个，我们称之为 "the left point"。此外，我们半独立地迭代 "right" 点，必要时移动 "start position"（参见步骤 #2）。
对于每个左边的点，从右边点的最后一个开始位置向上移动，并增加开始位置，直到我们进入 </code> 的范围（或者更确切地说<code>-) 根据Y 轴与左点的差异。 （注意："left" 和 "right" 点的分离使得必须从 - 开始）
现在从那个开始位置继续向上，计算到+之前所有点与当前左边点的距离。
第 2 步和第 3 步中完成的过滤使它成为 "data-dependent"。此实现中的权衡是您以更多 Y-checks 为代价进行更少的距离检查。代码也可以说更复杂。
为什么这个组合算法在 O(N) 中有效？出于同样的原因，在一个矩形 x2 中可以容纳多少个点有一个固定的界限（即 O(1)），这样每两个点之间的距离至少为 </code>。这意味着将在第 3 步进行 <code>O(1) 次检查。实际上，此算法检查的所有距离都将由 CLRS 版本检查，并且根据数据，还可能检查更多距离。
第 2 步的摊销成本也是 O(1)，因为整个外循环中第 2 步的总成本是 O(n)：您显然不能移动起始位置向上的次数比总次数 "right points" 多。
修改后的 CLRS 算法
即使在算法的 CLRS 版本中，您也可以轻松地对 #2 做出不同的决定。关键步骤的描述说：
- For each point
p in the array Y′, the algorithm tries to find points in Y′ that are within δ units of p. As we shall see shortly, only the 7 points in Y′ that follow p need be considered. The algorithm computes the distance from p to each of these 7 points and keeps track of the closest-pair distance δ′ found over all pairs of points in Y′
很容易将其修改为不检查 7 点，但首先检查 Y 中的差异是否小于 </code>。显然你仍然保证需要检查不超过 <code>7 点。同样，权衡是您进行较少的距离检查，但进行一些 Y-差异检查。根据您的数据和硬件上不同操作的相对性能，这可能是一个好的或坏的权衡。
其他一些重要想法
如果您不需要找到所有具有最小距离的对，您可以在过滤时安全地使用<`` instead of<=`
在使用浮点数表示的真实硬件世界中，= 的想法并不那么清晰。通常您无论如何都需要检查 abs(a - b) < έ 之类的内容。
我的反例背后的想法（针对不同的算法）：您不必将所有点都放在边缘上。边长为 </code> 的等边三角形可以放入大小为 <code>-έ 的正方形（这是 < 的另一种说法）
原答案
我认为您没有正确理解该算法中那个常数 7 的含义。实际上你不检查 4 或 7 或任何固定数量的点，你沿着 Y 轴向上（或向下）并检查落入相应矩形的点.很容易就会有 0 这样的点。对于算法在承诺的 O(n*log(n)) 时间内工作真正重要的是，在该步骤检查的点数有一个 固定 上限。只要你能证明，任何 constant 上限都可以。换句话说，重要的是该步骤是 O(n)，而不是特定的常量。 7只是相对容易证明的一种，仅此而已。
我认为 7 的实际原因是在实际硬件上您无法精确计算浮点数据类型的距离，您肯定会出现一些舍入误差。这就是为什么使用 < 而不是 <= 并不实用。
最后我不认为 4 是一个正确的界限，假设你可以可靠地做到 <。让我们假设 = 1。设 "left" 点为 (-0.0001; 0)，因此 "right" < 矩形为 0 <= x < 1 和 -1 < y < 1。考虑以下 5 个点（想法是：4 个点几乎在角上刚好适合矩形 < 和它们之间的距离 > ，第 5 个在矩形的中心）：
P1 = (0.001; 0.999)P2 = (0.999; 0.93)P3 = (0.001; -0.999)P4 = (0.999; -0.93)P5 = (0.5; 0)
请注意，这 5 个点之间应该大于 </code>，其中一些可能小于 <code> 来自 "left" 观点。这就是我们首先检查它们的原因。
距离P1-P2（对称地P3-P4）是
sqrt(0.998^2 + 0.069^2) = sqrt(0.996004 + 0.004761) = sqrt(1.000765) > 1
距离P1-P5（对称地P3-P5）是
sqrt(0.499^2 + 0.999^2) = sqrt(0.249001 + 0.998001) = sqrt(1.247002) > 1
距离P2-P5（对称地P4-P5）是
sqrt(0.499^2 + 0.93^2) = sqrt(0.249001 + 0.8649) = sqrt(1.113901) > 1
所以你可以在这样一个 < 的矩形中放置 5 个点，这显然比 4.
The Closest Pair of Points Problem 最近让我着迷。更具体地说，分而治之算法。
这个递归算法要求我将一组点分成两个块，a 和 b 并为每个块计算最接近的点对，然后计算它们之间最近的点对块和 return 这 3 个数量中的最小值。
计算块之间最近点的算法仅通过迭代最多 7 个点来工作，这些点最多 min(a, b) 远离 a 中的最后一个点（中位数元素整套）。
这两张图更能说明问题。 min(a, b) = Delta.
我知道如果我在 l 线上的两边都有 2 个点，a 和 b，我最多需要比较 7 个点中间条。
不过我想知道的是，如果我构造中间条带的点数严格小于距 l 的 Delta，难道我不能只比较接下来的 4 个点，而不是 7 个，因为我可以只适合 l 的每一侧 2 个点，小于 Delta 远离 l 和 Delta 彼此远离？
编辑： 我也在 cs stackexchange 上开始悬赏一个非常相似的问题，我们在那里进行了非常有趣的讨论。所以我将其链接 here. We've also started a very insightful chat here.
注意：根据与@Danilo Souza Morães 和@burnabyRails 的广泛讨论，此答案已更新以供将来参考，@burnabyRails 是 Danilo 提到的 accepted answer on a similar question by Danilo on the CS site. The main problem with the original answer is that I assumed that a bit different algorithm is used/discussed here. Since the original answer provided some important insights to Danilo it is preserved as is at the end. Also if you are going to read the discussion 的作者在他的回答中，请务必先阅读此处的介绍，以更好地理解我的意思。添加的前言讨论了所讨论算法的不同版本。
简介
该算法基于两个主要思想：
- 典型的递归分治法
- 事实上，如果您已经知道左右区域的最佳距离，您可以在
O(N)时间内执行 "combine" 步骤，因为您可以证明您可以对每个区域进行检查O(1)时间点。
尽管如此，在实践中有多种方法可以实现相同的基本想法，尤其是组合步骤。主要区别是：
- 您是否以不同的方式独立对待 "left" 和 "right" 点？
- 对于每个点，你是做固定数量的检查，还是先过滤候选项，然后只对过滤后的候选项进行距离检查？请注意，您可以在不中断
O(N*log(N))时间的情况下进行一些过滤，前提是您可以确保以分摊O(1)的方式完成过滤。换句话说，如果你知道优秀候选人的数量有一个很大的上限，你就不必检查确切的候选人数量。
CLRS Introduction to Algorithms 中算法的经典描述清楚地回答了问题 #1，因为您混合了 "left" 和 "right" 点并共同处理它们。至于#2，答案不太清楚（对我来说），但它可能意味着检查一些固定数量的点。这似乎是 Danilo 想问的问题的版本。
我想到的算法在这两点上都是不同的：它通过 "left" 点上升，并根据所有筛选的 "right" 候选者检查它们。显然，我在写答案时和最初的聊天讨论中并没有意识到这种差异。
"My"算法
这是我想到的算法的草图。
开始步骤很常见：我们已经处理了 "left" 和 "right" 点并且知道最好的
</code> 到目前为止，我们让它们沿 <code>Y轴排序。我们还过滤掉了所有不在±条带中的点。外层循环是我们向上遍历"left"点。现在假设我们处理一个，我们称之为 "the left point"。此外，我们半独立地迭代 "right" 点，必要时移动 "start position"（参见步骤 #2）。
对于每个左边的点，从右边点的最后一个开始位置向上移动，并增加开始位置，直到我们进入
</code> 的范围（或者更确切地说<code>-) 根据Y轴与左点的差异。 （注意："left" 和 "right" 点的分离使得必须从-开始）现在从那个开始位置继续向上，计算到
+之前所有点与当前左边点的距离。
第 2 步和第 3 步中完成的过滤使它成为 "data-dependent"。此实现中的权衡是您以更多 Y-checks 为代价进行更少的距离检查。代码也可以说更复杂。
为什么这个组合算法在 O(N) 中有效？出于同样的原因，在一个矩形 x2 中可以容纳多少个点有一个固定的界限（即 O(1)），这样每两个点之间的距离至少为 </code>。这意味着将在第 3 步进行 <code>O(1) 次检查。实际上，此算法检查的所有距离都将由 CLRS 版本检查，并且根据数据，还可能检查更多距离。
第 2 步的摊销成本也是 O(1)，因为整个外循环中第 2 步的总成本是 O(n)：您显然不能移动起始位置向上的次数比总次数 "right points" 多。
修改后的 CLRS 算法
即使在算法的 CLRS 版本中，您也可以轻松地对 #2 做出不同的决定。关键步骤的描述说：
- For each point
pin the arrayY′, the algorithm tries to find points inY′that are withinδunits ofp. As we shall see shortly, only the 7 points inY′that followpneed be considered. The algorithm computes the distance from p to each of these7points and keeps track of the closest-pair distanceδ′found over all pairs of points inY′
很容易将其修改为不检查 7 点，但首先检查 Y 中的差异是否小于 </code>。显然你仍然保证需要检查不超过 <code>7 点。同样，权衡是您进行较少的距离检查，但进行一些 Y-差异检查。根据您的数据和硬件上不同操作的相对性能，这可能是一个好的或坏的权衡。
其他一些重要想法
如果您不需要找到所有具有最小距离的对，您可以在过滤时安全地使用
<`` instead of<=`在使用浮点数表示的真实硬件世界中，
=的想法并不那么清晰。通常您无论如何都需要检查abs(a - b) < έ之类的内容。我的反例背后的想法（针对不同的算法）：您不必将所有点都放在边缘上。边长为
</code> 的等边三角形可以放入大小为 <code>-έ的正方形（这是<的另一种说法）
原答案
我认为您没有正确理解该算法中那个常数 7 的含义。实际上你不检查 4 或 7 或任何固定数量的点，你沿着 Y 轴向上（或向下）并检查落入相应矩形的点.很容易就会有 0 这样的点。对于算法在承诺的 O(n*log(n)) 时间内工作真正重要的是，在该步骤检查的点数有一个 固定 上限。只要你能证明，任何 constant 上限都可以。换句话说，重要的是该步骤是 O(n)，而不是特定的常量。 7只是相对容易证明的一种，仅此而已。
我认为 7 的实际原因是在实际硬件上您无法精确计算浮点数据类型的距离，您肯定会出现一些舍入误差。这就是为什么使用 < 而不是 <= 并不实用。
最后我不认为 4 是一个正确的界限，假设你可以可靠地做到 <。让我们假设 = 1。设 "left" 点为 (-0.0001; 0)，因此 "right" < 矩形为 0 <= x < 1 和 -1 < y < 1。考虑以下 5 个点（想法是：4 个点几乎在角上刚好适合矩形 < 和它们之间的距离 > ，第 5 个在矩形的中心）：
P1=(0.001; 0.999)P2=(0.999; 0.93)P3=(0.001; -0.999)P4=(0.999; -0.93)P5=(0.5; 0)
请注意，这 5 个点之间应该大于 </code>，其中一些可能小于 <code> 来自 "left" 观点。这就是我们首先检查它们的原因。
距离P1-P2（对称地P3-P4）是
sqrt(0.998^2 + 0.069^2) = sqrt(0.996004 + 0.004761) = sqrt(1.000765) > 1
距离P1-P5（对称地P3-P5）是
sqrt(0.499^2 + 0.999^2) = sqrt(0.249001 + 0.998001) = sqrt(1.247002) > 1
距离P2-P5（对称地P4-P5）是
sqrt(0.499^2 + 0.93^2) = sqrt(0.249001 + 0.8649) = sqrt(1.113901) > 1
所以你可以在这样一个 < 的矩形中放置 5 个点，这显然比 4.