c++ - R 和 B 被垂直线分隔时的双色最接近对(继续)

Question

Closest distance between two points(disjoint set)

在双色最近对问题中，我们在平面上得到一组 R 红色点和一组 B 蓝色点。问题是返回一对点，一红一蓝，其距离在所有红蓝对中最小。

我的算法就是其中的一种。

1: If both R and B store only a constant number of points, sort the points according to <y , com- pute a bichromatic closest pair using a brute- force algorithm, and return.

2: Assume |R| >= |B|, otherwise reverse the roles of R and B.

3: Pick a random element r from R.

4: Find the closest element of b in B to r.

5: Compute the left envelope of disks having radius |rb| centered at each of the points in B.

6: Remove all elements of R that are outside the envelope.

我想不出实现到 4、5、6 的任何想法。

一些引用说格雷厄姆的算法。我认为这不可能是一个圆圈。我想知道如何实现它们。

以及如何使信封成为某种区域？ T T..

在纸上画画很容易，但实现对我来说总是很难。有人用 C++ 提供建议吗？

Answer 1

我们仍在使用 L1 指标，对吧？假设红色点的 x <= 0 和蓝色点的 x >= 0。

每一对红蓝都有一条最多三段的最短路径:一条从红点到 y 轴的水平线段，一条在 y 轴上的垂直线段，一条从 y 轴到蓝点的水平线段。计算红点的 y 轴和 Voronoi 图的交点就足够了，然后在图中定位每个蓝点在 y 轴上的投影(例如，使用二进制搜索:P；它可能更快，但是，要按 y 坐标对蓝点进行排序并合并)。

    |
R****
    *
    *
    ******B
    |
    |y=0

假设一个红点 R = (x, y) 支配 另一个红点 R' = (x', y') 当且仅当 x' <= x (R 至少与到 y 轴为 R') 和 |y - y'| <= x - x'。

引理 1 如果 R 支配 R'，则 y 轴上的每个点至少与 R 一样接近 R'。

证明:令 P = (x, y')。基本上根据假设，d(R, P) <= d(R', P)。对于 y 轴上的每个点 Q，d(R', Q) = d(R', P) + d(P, Q) >= d(R, P) + d(P, Q) >= d (R，Q)。

         |
         Q
         *
R'**P*****
    *    |
    R    |

引理 2 令 R1 = (x1, y1), R2 = (x2, y2), R3 = (x3, y3)。假设 y1 <= y2 <= y3。如果 R3 支配 R1，则 R2 支配 R1 或 R3 支配 R2。对称地，如果R1支配R3，则R1支配R2或R2支配R3。

证明:我们有 x1 <= x3。分三种情况。

情况 1:x2 < x1。在这种情况下，x2 <= x3 和 |y3 - y2| <= |y3 - y1| <= x3 - x1 <= x3 - x2，所以 R3 支配 R2。

情况 2:x1 <= x2 <= x3。在这种情况下，|y2 - y1| + |y3 - y2| = |y3 - y1| <= x3 - x1 = (x2 - x1) + (x3 - x2)，所以 |y2 - y1| <= x2 - x1 和 R2 支配 R1 或 |y3 - y2| <= x3 - x2 和 R3 支配 R2。

情况 3:x3 < x2。在这种情况下，x1 <= x2 和 |y2 - y1| <= |y3 - y1| <= x3 - x1 <= x2 - x1，所以 R2 支配 R1。

引理3假设R支配R'，R'支配R，则R = R'。

引理 4 假设 R = (x, y) 不受其他红点支配。然后 (0, y) 比其他所有红点更接近 R。

---

总的来说，引理意味着通过重复消除所有 R' 和支配 R' 的某个邻居 R(按 y 坐标排序)，我们按顺序获得 Voronoi 单元。