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



Download 59 Kb.
Page1/10
Date16.05.2021
Size59 Kb.
  1   2   3   4   5   6   7   8   9   10

Finding the Closest Pair of Points
Problem: Given n ordered pairs (x1 , y1), (x2 , y2), ... , (xn , yn), find the distance between the two points in the set that are closest together.
The brute force algorithm is as follows:
Iterate through all possible pairs of points, calculating the distance between each of these pairs. Any time you see a distance shorter than the shortest distance seen, update the shortest distance seen.
Since computing the distance between two points takes O(1) time, and there are a total of = (n2) distinct pairs of points, it follows that the running time of this algorithm is (n2).



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