# 3.4. Miscellaneous

# Finding the Closest Pair of 2D Points

# 1. 내용

[J. Kleinberg and E. Tardos, Algorithm Design, Addison Wesley, 2005. 5.4]

• Problem
  • Given n points in the plane, find the pair that is closest together.
• Notation
• Naïve algorithm
  • Compute the distance between each pair of points
  • take the minimum → O(n^2) time

# 2. Applying the Divide-and-Conquer Strategy

• [Shamos and Hoey]
• Simple assumption for an easy explanation
  • No two points in P have the same x-coordinate or the same y- coordinate.
• General idea
  • [Preprocessing]
    • Build a list P_x in which all the points in P have been sorted by increasing x-coordinate→ O(n \log n)
    • Build another list P_y in which all the points in P have been sorted by increasing y-coordinate→ O(n \log n)
  • [Recursion for P with |P| = n]
    • [Divide] Partition P into two subsets Q and R → O(n)
    • [Conquer] Find the closest pairs in Q and R, respectively→ 2T(n/2)
    • [Combine] Use this information to get the closest pair in P→ O(n)
    • Time-complexity O(n \log n) + T(n) where T(n) = cn +2T(n/2) → O(n \log n)
• The stage [Divide]: Partition P into two subsets Q and R.
  • Create Q and R, where
    • Q: the set of points in the first \lceil(n/2)\rceil positions of the list P_x (the “left half”),
    • R: the set of points in the final \lfloor(n/2) \rfloor positions of the list P_x (the “right half”).
  • Furthermore, create Q_x, Q_y, R_x, and R_y, where
    • Q_x consisting of the points in Q sorted by increasing x-coordinate,
    • Q_y consisting of the points in Q sorted by increasing y-coordinate,
    • R_x consisting of the points in R sorted by increasing x-coordinate,
    • Ry consisting of the points in R sorted by increasing y-coordinate.
  • ✓ Can be done in O(n)
• The stage [Conquer]: Find the closest pairs in Q and R, respectively.
  • Recursively determine a closest pair (q_0, q_1) of points in Q.
  • Recursively determine a closest pair (r_0, r_1) of points in R.
    • Can be done in 2T(\frac n 2).
• The stage [Combine]: Use the obtained info. to get the closest pair in P.
  • Question : are there points q \in Q, r \in R for which d(q,r)<\delta?
    • How can we answer this question in linear time?
  • [Fact 1] (Why?)
    • if there \exists q \in Q , r \in R for which d(q,r)<\delta
    • then each of q,r lies within a distance \delta of$ L$
  • [Fact 2]
    • \exists q \in Q, r\in R for which d(q,r)<\delta \iff \exists s, s^{'} \in S for which d(s,s^{'})<\delta
    • 
    • x^*: the x-coordinate of the rightmost point in Q
    • \delta=min(d(q_0^*,q_1^*),d(r_0^*,r_1^*))
    • 
  • [Fact 3]
    • if s, s^{' } \in S have the property that d(s, s^{'})<\delta, then s, s^{'} re within 15 positions of each other in the sorted list S_y
      • S_y : the list consisting of the points in S sorted by increasing y-coordinate.
      • Each box contains at most one point of S. (Why?)
      • If two points in S are at least 16 positions apart in S_y , ...
    • 
  • [merge] : O(n)
    1. For each s \in S_y , compute its distance to each of the next 15 pts in S_y
    2. Let s, s^{'} be the pair achieving the minimum of these distances
    3. Compare d(s, s^{'}) with \delta
    •