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.


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 )

Google+ photo

You are commenting using your Google+ 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 )


Connecting to %s


%d bloggers like this: