1. 9 points Consider the following problem: Given a set of n points in the plane
ID: 3914735 • Letter: 1
Question
1. 9 points Consider the following problem: Given a set of n points in the plane, pi (z?, y?), ?? = (x2,U2), . . . , pn-(Xn,Yn), determine which pair pi, pi are closest. distance between any two points, Pa = (Ža,y),Po = (??, ??) in the plane is The Write pseudocode to determine the two closest points among a collection of n points. Analyze it by: identifying the input/input size, identifying the elementary operation and how often it gets it gets executed with respect to the input size and provide an asymptotic characterization.Explanation / Answer
Pseudocode is as follows:
input n points
store it in X[] and Y[] // to store x and y co-ordinates
declare indexi, indexj // to store the index of closest points.
declare min = 1000000 (largr number)
Loop: i := 1 to n for each point we will find its distance with all the other points
Loop:j:= 1 to n
if sqrt((X[i]-X[j])*(X[i]-X[j]) + (Y[i]-Y[j])*(Y[i]-YX[j])) < min
min = sqrt((X[i]-X[j])*(X[i]-X[j]) + (Y[i]-Y[j])*(Y[i]-YX[j]))
indexi = i
indexj = j
ends
ends
output(X[indexi],Y[indexi] , X[indexjj], Y[indexj])
The basic operation is calculating distance and comparison
The complexity is of the O(n^2) as every point is considered with every point.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.