Divide and Conquer(Find two closest dots)

I searched up Internet and I got a nice information out of it. So my writing will basically, explain the information from it.

The link is -> http://www.cs.ucsb.edu/~suri/cs235/ClosestPair.pdf


It’s a pretty interesting topic in Divide and Conquer(let’s call it DC), I think.

Because, you need to use this to solve many problems.

For example, to make a nice navigation system, you want to know the most fastest way to get to a some point from the present position. Something like that.

There can be many approach to solve this problem.

One of the most naive one will take O(n^2).

For each dot, you will check the distance from it to every other dots.

Can we do better than this?

Yes, by using DC!

Let’s think about the 1-d case first.

First, we sort the point first and divided them as a half.

Second, get the pair with the minimum length from the left and another pair from the right.

So now you might want to compare two things and get the minimum out of it but..


There might be a case that the distance of one point from the one side and the point from the other side is the closest pair!

Let’s say we found “%” is the minimum length from S1 and S2. Then, we just need to check the distance of dots in the range of  (m-%, m+%) where m is the mid line.

You might say,

“Well… what if there are a lot of dots in the S1 side that are in the range?”

No! there can be only 1…

If there were more than 1 in the one side, well then they have smaller length then % and it’s contradict our observation.

So there is only one in the (m-% m] and another one [m, m+%), So we need to check only two dots.

So the pseudo code is like below.

The running time for Closest-Pair is O(1) and we need to compare all the input and get the mid point so it’s O(n) work, the total running time will be like this.

T(n)= 2*T(n/2) + O(n)

By using the master theorem,

b = 2, a= 2 and c = 1 hence, 0(nlogn).

2-d case is very similar with this, the only reason I’m doing this is for my term test.

So yes, as you can see now it’s 2-d ,but all the same. (Except for one thing, actually)

We just need to make a mid line according to the one coordinate.

Either x or y doesn’t really matter.

The thing that has changed is the number of dots that can be around the mid line, when we need to check them.  But don’t worry, the points in the P1 and P2 have a bit interesting feature with them.

To find a point to be the closest pair in the other side, p have two box to check.( i.e., check upside and downside to the left side. )

And the box can only contain up to 6 points.

For one side there can be 2/n points, and for each point for 2/n points there are 6 points at the other side to get the distance from it.

Nasty! Right?

I do agree. CS is very powerful but super Nasty….. :S

But it will pay off… hopefully!

If you ask why there are 2/n points at one side just think, that we divide n points by half

so for each side there are n/2 points and for the worst case they are all in the range of

delt/2 from the mid line.

So the comparing took 6* n/2  hence it’s O(n).

So T(n) = T(n/2) + T(n/2) + O(n)

T(n/2) => get the closest pair from the one side

Okay by the 2-d, we can go for n-d but I don’t want to right now..

This is done for today!


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: