algorithm - 最近的对 - 太多点？

Question

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

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

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

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

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

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

Answer 1

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

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

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