  Don't use plagiarized sources. Get Your Custom Essay on
GET AN ESSAY WRITTEN FOR YOU FROM AS LOW AS \$13/PAGE

Given in points in the plane, consider the problem of finding the pair of points that is closest together. One algorithm for doing this is the brute-force method: list all the pairs, compute their distances, and take the smallest one. (i) Explain how this brute-force algorithm can be implemented without ever computing a squareroot . (ii) Implement this algorithm in Python (without using squareroot s). Your code should accept a list of points (ordered pairs (x_i, y_i) of floats) and return the two points that are closest together. (iii) Show that this algorithm has temporal complexity in O(n^2) (where the fundamental operations include basic arithmetic operations +, -, times, /, assigning a value to a variable or to a given position in a list, looking up the value of a particular element at a given position in a list, comparing two values, and incrementing a value). Surprisingly, there is a O(n log n) algorithm for solving this problem (see [KT05, 5.4]).

Solution=====================

1) Square root is not important, as we only need to know, which two points are relatively closer. Even if we stop to the of the distance formula’s step, where both x and y are squared and added. We can get away with using this “distance^2” for comparisons, rather than square rooting them to “distance”.

2)

def getClosestPair(pairs):
point1=()
point2=()
smallestDistanceSq=sys.maxint

for i in range(len(pairs)):
for j in range(i+1,len(pairs)):
xDistance=pairs[i]-pairs[j]
yDistance=pairs[i]-pairs[j]
#just comparing with squares, no need of rooting
distanceSq=(xDistance*xDistance)+(yDistance*yDistance)

if(distanceSq<smallestDistanceSq):
point1=pairs[i]
point2=pairs[j]
smallestDistanceSq=distanceSq

print(point1)
print(point2)
print(smallestDistanceSq) 3)As we can see that, the outer loop iterates for each number of pairs(N), while the inner loop also does the same. Making it N*N = O(N^2). Since the complexity of other operations(like +,- etc.) are trivial/constant to this, they as per rule, are simply discarded for computing time complexity.