algorithm - closest pair of points using Manhattan distance -

algorithm - closest pair of points using Manhattan distance -

i going through section in coreman describes using split , conquer approach find closest pair of points using euclidean distance between 2 points.

there problem asks find closest pair of points using manhatten distance between 2 using similar approach. however, not able grasp difference between two. next think of:

1) x , y 2 arrays points sorted on x- , y- coordinates respectively.

2) find line 'l' divides set of points between subset pl , pr points less or equal 'l' going pl , otherwise pr. utilize xl , xr 2 arrays containing points pl , pr. same goes yl , yr.

3) recurse till our subset of points <= 3 (use brute forcefulness in case)

4) minimum distance 1 returned of recursive calls - phone call d.

5) find points within 2d width around line 'l' , each such point find manhatten distance (all ??) points within strip ?

6) homecoming minimum step (5) , (4)

it in step 5) stuck. not able figure out logic behind choosing number of points compare with.

to more specific: mentioned in coreman euclidean distances, need check 7 points, , after searching on google this reference states manhattan distances, need consider 12 points. unable understand logic of how selection of points dependent on type of distance seeking.

for each point in left part of l, there @ 6 points in right distance less d. these 6 points can positioned @ 6 corners of 2 squres . 1 more, pair distance less d can found.

then sort points in right side of l y-coordinates. find 6 points closest p in y-axis, may produce closer distance.

algorithm computational-geometry