algorithm - 最接近的一对 - 点数太多？

让我们稍微检查一下这张图片。

基本上，我们遵循众所周知的步骤:对点进行排序，将点数组分成两半，然后递归计算与右侧和左侧的最小距离。
我们认为 δ 是两个计算距离中的最小值。
让我们从左侧考虑一个点 p 。现在我们有这些假设:
“从右侧开始，在 p δ 距离内的所有点都位于 δ x 2δ 矩形 R 中。如果每对至少相距 δ，则 R 内最多有 6 个点”。

这些假设有点模棱两可。
1 。我们究竟应该在哪里放置矩形？ A 应该是 p 在边界上的投影吗？

2 。 “内部” R 的 6 个点实际上是矩形的顶点和中点的 2 个？

3 。为什么红圈内的3分是候选人？从 A 到顶点的距离是 δ√2 > δ。如果我们考虑 p 和 A 之间的距离是 x ，那么 p 和另一个点(中点)之间的距离将是 x + δ > δ。

资料来源:https://www.cs.ucsb.edu/~suri/cs235/ClosestPair.pdf

最佳答案

矩形应该放在区域 P2 中，是的，A 应该是 p 在边界上的投影。矩形的左侧应与中线重合。

6 个点是区域 R 中可以找到的最大点数，因为任意两对点之间的最小距离是 delta。如果有 6 个点，那么这些点的位置应如您所描述的那样。

可能存在 p 与 A 重合的情况。因此我们知道，除了最右边的两个顶点之外，其他 4 个点都可以是有效候选点。现在顶点上的点本身不能成为候选点，但它们作为我们应该考虑为候选点的点的边界。