Posted by: atri | November 30, 2009

Lect 34: Algorithm for closest pair (post #1)

(Guest post by Anthony  Consiglio)

We started off lecture by going through the slides that were made available over the weekend.

We then discussed how to split P_x and P_y into Q_x, Q_y, R_x, R_y in linear time. It was also clarified that the dividing line between Q and R  can be defined as the “farthest right” point of Q.

Note: Euclidean distance between points, which says that the distance between two points is greater than either the x distance or the y distance between them.

After Q and R are separated, we need to look at all points within \delta of the Q/R border. The slides show all possibilities of arrangements of points in relation to the \delta rectangle from the Q/R border. It should also be noted the y values of those lines go from negative infinity to positive infinity.
The problem faced here is that S, which is the area described above, could still be P. Let $latex  x^*$ be the x coordinate of the “last” point in Q.  At this point we set up a recurrence relation for everything up to this point, and noted that section 5.2 in the book shows how to solve them.

Cool Lemma:
Let s, t be elements in S. if d(s,t) < \delta, then   s and tare within 15 positions of each other in S_y.

Note: S_y can be found in O(n) time. Note that we only need to find  s^*,t^*\in S such that d(s^*, t^*) < \delta (if any). Assume that \delta >0.

(Recall \delta = \min(d(q_0^*, q_1^*), d(r_0^*, r_1^*)).)

Proof of Cool Lemma:

Claim1: If s, t are in S and are at least  16 positions apart in S_y, then d(s,t) > (3\delta / 2) > \delta.

Proof idea: Divide \{x^* - \delta < x < x^* + \delta\} [into \frac{\delta}{2}\times \frac{\delta}{2} boxes/squares.–Atri]

Claim 2: Cannot have s \neq t \in S in one square. If not, d(s,t) \le \frac{\delta \sqrt{2}}{ 2} =\frac{ \delta }{\sqrt{2}} < \delta, which is a contradiction to the definition of \delta.
Fun Fact: \sqrt{2} > 1

This means that any square may contain either s or t, but not both.

Proof of claim 1: Assume s, t \in S such that they are at least 16 positions away. Since all the boxes are \delta/2 in distance, anything over 15 positions away would be more than \delta in distance.


Leave a Reply

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

You are commenting using your 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: