HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Understanding Closest Pair Algorithm (CLRS)

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
understandingclrsalgorithmclosestpair

Problem

I'm reading CLRS Section 33.4 Finding the closest pair of points. At exercise
33.4-2 they say


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.

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.