一条线上最近的一对点

Question

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

有谁知道适用于欧几里德距离的类似算法？

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

有任何想法吗？

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