patternMinor
Understanding Closest Pair Algorithm (CLRS)
Viewed 0 times
understandingclrsalgorithmclosestpair
Problem
I'm reading CLRS Section
33.4-2
Show that it actually suffices to check only the points in the 5 array positions following each point in the array Y'
But I'm getting 4 array positions following each point in the array Y' will be suffice to check. See the fig below
Which possibility I'm missing. Can anybody point it out.
33.4 Finding the closest pair of points. At exercise 33.4-2 they say33.4-2
Show that it actually suffices to check only the points in the 5 array positions following each point in the array Y'
But I'm getting 4 array positions following each point in the array Y' will be suffice to check. See the fig below
Which possibility I'm missing. Can anybody point it out.
Solution
Assume that a point exists in every corner in the figure (including the inside corners). If points cannot overlap, then you have 6 points that can reside in the x2 box, and since you must be looking at one of them, you need only compare it to the next 5 in Y'.
Context
StackExchange Computer Science Q#47697, answer score: 3
Revisions (0)
No revisions yet.