What is the fastest way of finding sum of two coordinates from two different sets with some criteria?

user_4328035 0
Viewed 154

I have two sets as below. What is the best way to find all coordinates one from each set whose sum is atleast H. 

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

if the answer is (x1,y1) and (p1,q1) then it should meet x1+p1>=H and y1+q1>=H. I need to find out all such coordinates (only count).

Example:

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 Approach: I can use two for loops to go through all combination of two sets A and B. But this is O(N^2) solution.

I know another technique in which I can sort set B on x-coordinates. So that from A, I can pick up each x-coordinate and will check in B for H-x, identifying H-x can be done in long n but from there I need to count one by one to check whether y-coordinate is meeting the condition or not.

Is there any better solution for this?

graph-algorithm algorithm
1 Answers

If I am right, a range-tree can be used to solve the "dominant point counting", i.e. telling how many points in a 2D set have coordinates x>a and y>b (see Shamos & Preparata, Computational Geometry, p.40 + Section 2.3.4). After O(N Log N) preprocessing time and with O(N Log N) storage, a query can be answered in time O(Log²N).

Hence, by trying all points of the second set in turn and using the above data structure to count the point of the first set such that xj>h-pi, yj>h-qi, you can achieve the global complexity O(N Log²N).

user_11965490
Related