algorithm - 根据某些标准从两个不同的集合中找到两个坐标之和的最快方法是什么？

Question

我有两套如下。从总和至少为 H 的每个集合中找到所有坐标的最佳方法是什么？

A = {(x1,y1), (x2,y2),....(xn,yn)}
B = {(p1,q1), (p2,q2),....(pn,qn)}

如果答案是 (x1,y1) 和 (p1,q1) 那么它应该满足 x1+p1>=H 和 y1+q1>=H。我需要找出所有这些坐标(仅计数)。

例子:

A = {(2,3), (1,6), (5,2), (10,1)}
B = {(5,6), (8,4), (3,5), (1,9), (7,7)}
H = 8
Answer: 7
Explanation:
    {
    {(1,6),(8,4)},
    {(1,6),(7,7)},        
    {(2,3),(7,7)},
    {(5,2),(5,6)},
    {(5,2),(7,7)},
    {(10,1),(1,9)},
    {(10,1),(7,7)}
    }

蛮力方法:我可以使用两个 for 循环来遍历两组 A 和 B 的所有组合。但这是 O(N^2) 解决方案。

我知道另一种技术，可以在 x 坐标上对集合 B 进行排序。这样我就可以从 A 中取出每个 x 坐标并在 B 中检查 Hx，识别 Hx 可以在 long n 中完成，但从那里我需要一一计数以检查 y 坐标是否满足条件或不是。

有没有更好的解决方案？

Answer 1

如果我是对的，可以使用范围树来解决“优势点计数”，即告诉 2D 集中有多少点具有坐标 x>a和 y>b (参见 Shamos & Preparata，计算几何，第 40 页 + 第 2.3.4 节)。后 O(N Log N)预处理时间和用O(N Log N)存储，有问题可以及时解答O(Log²N) .

因此，通过依次尝试第二组的所有点并使用上述数据结构来计算第一组的点，使得 xj>h-pi , yj>h-qi ，可以实现全局复杂度O(N Log²N) .