P ROBLEM D ESCRIPTION : Consider a set of points in a typical X-Y Cartesian plan
ID: 3665523 • Letter: P
Question
PROBLEM DESCRIPTION: Consider a set of points in a typical X-Y Cartesian plane. Each point has an identifier (I suggest just using integer values such as p1, p2, p3, and so on...), and x and y coordinates as usual. Present a problem discussion, solution discussion, and algorithm for the following two tasks:
Closest Pair: Find the two points that are closest to each other. Return the points, their x and y coordinates, and the distance between them.
Bounding Rectangle: Find the smallest rectangle that will contain the set of points. Points may lie on the rectangle boundary (as opposed to being strictly inside the rectangle). Define the rectangle using the x and y coordinates of the upper left and lower right corners. Return the coordinates of those points. The sides of the bounding rectangle are parallel with the X- and Y- axes.
Explanation / Answer
distance(p1, p2):
return sqrt(((p1.x - p2.x) * (p1.x - p2.x)) + ((p1.y - p2.y) * (p1.y - p2.y)))
closest_pair(P):
// P is array of points
p1, p2 //closest points
min_distance = Inf // initialize min_distance to infinity
for i in P:
for j in P:
if i != j and distance(i, j) < min_distance:
min_distance = distance(i, j)
p1 = i
p2 = j
end
end
end
return p1, p2
area(p1, p2):
return abs(p1.x - p2.x) * abs(p1.y - p2.y)
minimum_rectangle(P):
p1, p2
min_area = Inf
for i in P:
for j in P:
if i != j and area(i, j) < min_area:
min_area = area(i, j)
p1 = i
p2 = j
end
end
end
return p1, p2
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.