Algorithm for 2-D closest co-ordinates

Question

I know I am doing this wrong, but cannot think of the right way to solve this problem. I am working with 12 points listed below. (1,2)(1,11)(7,8)(9,9)(12,13),(13,4),(20,8),(22,3),(23,12),(24,14),(26,7),(31,10)

I divide this into two subsets

Left = (1,2)(1,11)(7,8)(9,9)(12,13),(13,4)

Right=(20,8),(22,3),(23,12),(24,14),(26,7),(31,10)

Further cut down

LLeft=(1,2)(1,11)(7,8)

RLeft=(9,9)(12,13),(13,4)

LRight=(20,8),(22,3),(23,12)

RRight=(24,14),(26,7),(31,10)

Find the min distance on each set.

LLeft (1,2)(1,11) is 9, (1,11)(7,8) is 6.7, (1,2)(7,8) is 8.48

The min is 6.7

RLeft (9,9)(12,3) is 6.70, (9,9)(13,4) is 6.4, (12,3)(13,4) is 1.14

The min is 1.14

LRight (20,8)(22,3) is 5.38 (20,8)(23,2) is 5, (22,3)(23,12) is 9.05

The min is 5

RRight (24,14)(26,7) is 7.28 (24,14)(31,10) is 8.06 (26,7)(31,10) is 5.83

The min is 5.83

So now I have LLeft, RLeft, LRight, and RRight. What I need to find is LRLeft, RLLEft_Right(value in the middle) and LRRight.This is where I get confused. The only way I can think of getting LRLeft is to take every point in LLeft and RLEft and find the distance between the two. Then use that distance and compare that with LLeft and RLeft and this will give me the shortest distance between two point for the left side. Then I do the same for the right and center. I am pretty sure there is a quicker and better way to do it, but I cannot figure it out.

Answer 1

You should take a look at http://en.wikipedia.org/wiki/Closest_pair_of_points_problem#Planar_case

Here's a better resource for Step 4, but to get you started: In the recursion, if we already have minimum distances d1 and d2 within the left and right sets respectively, then if there is a closer pair of points - where one is from the left and one is from the right set - then we only need to check points within a distance d of the dividing line, where d = min(d1,d2).