Finding the Closest Pair of Points Problem: Given n ordered pairs x1, y


Finally, we must merge ALL the points together by y-coordinate



Download 59 Kb.
Page8/10
Date16.05.2021
Size59 Kb.
1   2   3   4   5   6   7   8   9   10
Finally, we must merge ALL the points together by y-coordinate:
(0, 0), (8, 0), (5, 1), (2, 3), (3, 4), (7, 4) , (1, 6), (6, 7), (2, 8)
this time, we only pick those points that are within of the line x=2 to copy into v. These points are:
(0, 0), (5, 1), (2, 3), (3, 4), (1, 6), (2, 8)
Now, we scan through all pairs to discover that the shortest distance between any of the two points is .

Strassen’s algorithm:Matrix multiplication

The standard method of matrix multiplication of two n x n matrices takes T(n) = O(n3).






Share with your friends:
1   2   3   4   5   6   7   8   9   10




The database is protected by copyright ©essaydocs.org 2020
send message

    Main page