如何以最快的方式找到两个不同集合中符合某些条件的坐标之和？

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中检查H-x，识别H-x可以在长n时间内完成，但从那里我需要逐一计数以检查y坐标是否符合条件。

是否有更好的解决方案？

- chindirala sampath kumar

---

感谢 H 的卓越贡献！ - chindirala sampath kumar

是的，所有都是正数。 - chindirala sampath kumar

首先，B中任何大于H的坐标都将被设置为H。例如，(1,9)会变成(1,8)。然后问题是有多少个B中的点在给定矩形内。对于A的第一个元素(2,3)，问题是有多少个B中的点在矩形(6,5)到(8,8)内。我猜您需要像k-d树这样的空间分区树来快速回答这些查询。 - user3386109

O(N²)并不一定是一种糟糕的复杂度，因为确实存在N²个解决方案。在这种情况下，暴力搜索是最优解。 - user1196549

注意，坐标对列表（在示例说明中显示）不是算法的输出。输出是一个数字：7。没有必要枚举所有的对来确定计数。 - user3386109

@user3386109：你是对的。 - user1196549

Answer 1

如果我没错的话，可以使用range-tree来解决“主导点计数”问题，即告诉我们在一个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)。

- user1196549