从两个不同的集合中寻找两个坐标之和的最快方法是什么，有什么标准？

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)}
    }

Bruteforce方法。 我可以使用两个for循环来检查两个集合A和B的所有组合。但这是O(N^2)的解决方案。

我知道另一种技术，我可以在x坐标上对B集进行排序。我知道还有一种技术，我可以将B集以x为坐标进行排序，这样从A中提取每个x坐标，然后在B中检查H-x，识别H-x可以用长n来完成，但是从那里开始我需要一个一个地数来检查y坐标是否满足条件。

有什么更好的解决方法吗？

Answer 1

如果我没说错的话，可以用范围树来解决 "显性点计数"，即告诉一个2D集合中有多少个点的坐标为 x>a 和 y>b (见Shamos & Preparata, Computational Geometry, p.40 + Section 2.3.4)。在 O(N Log N) 预处理时间，并且有 O(N Log N) 存储，可以及时回答查询 O(Log²N).

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