跨越一条直线的最近点对

Question

我有两组二维点，它们被平面上的一条线分开。我想高效地找到一对点，其中一个来自每组点，它们之间的距离最小。Radu Litiu有一篇非常方便的论文，Closest Pair for Two Separated Sets of Points，但它使用的是L1（曼哈顿）距离度量而不是欧几里得距离。

有人知道类似的算法可以使用欧几里得距离吗？

我大概可以看出标准分治最近对算法的扩展——通过与原始分割线垂直的中位线将两个集合分开，对两侧进行递归，然后查找由中位线两侧的一个点组成的更近的一对。如果递归步骤中的最小距离为d，则伴随着中位线一侧的点的配对必须在一个尺寸为2d*d的盒子内。但与原始算法不同的是，我看不到任何限制该盒子内点数的方法，因此整个算法变成了O(m*n)。

有什么想法吗？

- Sneftel

---

我们谈论的是多少个点？ - גלעד ברקן

其中的N个。 :-) 在某些情况下，一个简单的 m*n 暴力扫描可能会有最佳的墙钟性能，但我也对从更理论的角度来看这个问题很感兴趣。 - Sneftel

Answer 1

Evgeny的回答有效，但没有库的支持需要付出很大努力：计算完整Voronoi图再加上额外的扫描线算法。更容易的方法是枚举两个点集中与隔离线相交的Voronoi单元格中的点，并按顺序进行测试，然后通过线性时间合并步骤测试它们之间所有相交的细胞中的点对。

为了计算所需部分的Voronoi图，假设X轴是隔离线。按x坐标对点集进行排序，舍弃y较大的等于某个其他点的x坐标。按照x坐标的顺序开始扫描点，将它们推入堆栈。在推入之间，如果堆栈至少有三个点，比如p、q、r，其中最近推入r，就测试连接pq的线是否在连接qr的线之后与隔离线相交。如果是，则丢弃q，并使用新的顶部三个重复测试。粗略的ASCII艺术：

Case 1: retain q

------1-2-------------- separating line
     /  |
  p /   |
   \    |
    q-------r

Case 2: discard q

--2---1---------------- separating line
   \ /
  p X r
   \ /
    q

- David Eisenstat

---

哦，那就更好了。如果这些点已经相对于分离线进行了预排序（实际上可能已经排好序了，我需要检查一下），那么这似乎可以将算法降到线性时间。非常棒！ - Sneftel

Answer 2

对于集合中的每个点，找到另一个集合中最接近的点。在此过程中，仅保留距离最小的一对点。这将给定的问题简化为另一个问题：“查找集合A中所有点在集合B中最近的邻居的算法”，可以使用扫描线算法解决(1) 一组点和(2) Voronoi图形的其他集合。

算法复杂度为O((M+N) log M)。该算法不使用两组点之间被一条线分隔的事实。

- Evgeny Kluev

---

啊，聪明。所以先构建 Voronoi 图，然后进行扫描，并使用扫描将点与 Voronoi 区域关联起来，而不需要为每个点进行单独的最近邻搜索。很棒的答案！ - Sneftel

Answer 3

那么这个呢：

1. 确定任意点在哪一侧：

   • 让P是您的点(P0,...Pi,...Pn)
   • 让A、B是分离线起始-结束点
   • 因此：side(Pi) = ((B-A).(Pi-A))的标志
   • 这基于一个简单的事实，即数量积（点乘）的符号取决于点的顺序（有关三角形/多边形绕组规则的信息，请参见）。

2. 找到任何(side(Pi)!=side(pj)) (Pi,Pj)的最小距离

   • 首先为所有点计算所有边(O(N))
   • 然后循环遍历所有Pi，并在其中进行
   • 循环遍历所有Pj并搜索最小距离。
   • 如果Pi和Pj组近似相等大小，则O((N/2)^2)

3. 您可以通过从AB“排序”点Pi、Pj的“距离”来进一步优化搜索

   • 您可以使用另一个点积来完成这个过程，这次不是(B-A)
   • 使用垂直于它的向量，比如(C-A)
   • 丢弃所有来自Pi2(和类似的Pj2)的点
   • 其中((B-A).(P(i1)-A))接近于((B-A).(P(i2)-A))
   • 并且|((C-A).(P(i1)-A))| << |((C-A).(P(i2)-A))|
   • 因为这意味着Pi2在Pi1后面(离AB更远)
   • 而靠近走向Pi1的AB正常
   • 此优化后的复杂度强烈依赖于数据集。
   • 应该是O(N+(Ni*Nj))，其中Ni/Nj是剩余点Pi/Pj的数量
   • 您需要2N个点积，Ni*Nj距离比较（不需要sqrt）

- Spektre

---

第二步的时间复杂度为O(mn)。有更简单的解决方案，其时间复杂度也为O(mn)。 - Philip

是的，因此有第三步替换第二步。但是它仍然是O（N+m*n）。但是N和m、n之间的相关性是未知且非线性的。 - Spektre

这里的暴力解法有些我想要避免的。我可以使用到目前为止最佳距离来修剪每个点的搜索窗口，但这并不能提供任何保证。 - Sneftel

Answer 4

（我不确定这是否与David的想法有任何相似之处...我登录后才看到它，以发表我的想法。）为了论证，让我们假设我们将所有内容转置，使分界线为x轴，并按x坐标对点进行排序。假设N不是太大，如果我们沿着x轴扫描（即遍历我们排序过的a和b的列表），我们可以记录整体最小值和两个已通过点的列表。扫描中的当前点会与另一个列表中的每个已通过点进行测试，同时从列表中的点到（我们的扫描的x坐标，0）的距离大于或等于整体最小值。在下面的示例中，当到达b2时，我们可以停止在a2处进行测试。

        scan ->                 
      Y                           
      |         a2         
      |                   
      |   a1           a3   
X--------------------------
      |     b1           b3
      |             b2

- גלעד ברקן

Answer 5

一种典型的解决方案是扫描线算法。假设您有一个包含所有点和分离点的线的坐标系。现在想象一条垂直于分离线的线按升序从点到点跳跃。为了方便起见，您可以旋转和平移点集和分离线，使分离线等于x轴。扫描线现在与y轴平行。

使用扫描线从点到点跳跃时，跟踪两个不同集合中的两个点之间的最短距离。如果前几个点都来自同一集合，则很容易找到一个公式，告诉您必须记住哪个点，直到遇到来自另一个集合的第一个点。

假设您总共有N个点。您将需要在O(N*log(N))中对所有点进行排序。扫描线算法本身将在O(N)中运行。

- Philip

---

我不确定那是否是最小欧几里得距离...在欧几里得空间中，每一侧最近的点到分隔线可能比最近的点到分隔线更远。这有点抽象，图像可能更好，也许我对问题的理解与我应该的不同。 - Spektre

不确定如何在这里使用扫描线算法...当按y顺序处理新点时，您如何在常数时间内确定另一组中最近的点是什么？ - Sneftel

@Ben：通过跟踪最短距离，如果到另一个集合的最后一个点的新距离更大，则继续。如果不是，则这就是新的最短距离。 - Philip