*(Guest post by Michael Impson)*

- Sort by -coord
- to get ( is sorted by -coord)
- Divide into and
- are the first points in
- is

You want to recursively find the closest pair

- Divide into and
- Recursively figure out closest pair in and in
- “Patch up” to get closest pair overall

*Question:* time to compute from and

- In order to check to see if it’s in : if in , then is in , else it is in

Define .

If for all , , 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 .– Atri]*

**Lemma:** For any , iff .

Advertisements

## Leave a Reply