Posted by: atri | November 23, 2009

## Lect 33: Closest points in 2-D (post #2)

(Guest post by Michael Impson)

• Sort $P$ by $x$-coord
• $O(n\log n)$ to get  $P_x$    ($P_y$ is $P$ sorted by $y$-coord)
• Divide $P$ into $Q$ and $R$
• $Q$ are the  first $\lceil n/2\rceil$ points in $P_x$
• $R$ is  $P\setminus Q$

You want to recursively find the closest pair

1. Divide $P$ into $Q$ and $R$
2. Recursively figure out closest pair $(q_0^*, q_1^*)$ in $Q$ and  $(r_0^*, r_1^*)$ in $R$
3. “Patch up” to get closest pair overall

Question: $O(n)$ time to compute  $Q_x,Q_y,R_x,R_y$ from $P_x$ and $P_y$

• In order to check to see if it’s in $R_y$: if in $P_y$, $x_i \le x^*$ then $(x_i,y_i)$ is in $Q_y$, else it is in  $R_y$

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

If  for all $q \in Q, r \in R$, $d(q,r) \ge \delta$, then we are done!

Otherwise note that for any such pair, $\delta> \sqrt{(x_q-x_r)^2+(y_q-y_r)^2}\ge |x_q-x_r|$.

[Define $S=\{(x,y)\in P| |x-x^*|\le \delta\}$.– Atri]
Lemma: For any $q\in Q, r\in R$, $d(q,r) < \delta$ iff $q,r \in S$.