algorithm - 一条直线上最近的一对点

Question

我有两组二维点，它们在平面上被一条线隔开。我想有效地找到一对点，​​由每组中的一个点组成，它们之间的距离最小。 Radu Litiu 有一篇看起来非常方便的论文，两个分离点集的最近对，但它使用 L1(曼哈顿)距离度量而不是欧氏距离。

有人知道适用于欧氏距离的类似算法吗？

我几乎可以看到标准分而治之最接近对算法的扩展——用垂直于原始分割线的中线划分两组，在两侧递归，然后寻找更接近的对，包括从中位数的每一侧开始一个点。如果与递归步骤的最小距离为 d，则中位数一侧的点的伴点必须位于尺寸为 2d*d 的框内。但与原始算法不同的是，我看不出有任何方法可以限制该框中的点数，因此整个算法就变成了 O(m*n)。

有什么想法吗？

Answer 1

Evgeny's answer可行，但如果没有库支持，需要付出很多努力:计算完整的 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