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 $t$are 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.