Jaehyeon

Heo

(Teddy)

Master Theorem

Closest pair of points

Problem Statement

Input: set $P = \{p_1, \dots, p_n\}$ of $n$ points $P$ in the plane; $$

Goal: output $p_i, p_j\in P, i\neq j$, minimizing the the Euclidean distance $dist(p_i, p_j)$

Applying Divide and Conquer Algorithm (Attempt #1)

• Divide: divide P into equal size parts Q and R with a vertical line L
• Recurse find the closest pairs in Q and from r
• Combine: output the closer pair among those two

Notice that this attempt is a failed attempt, as if the closest pair is between two points from Q and R, this fails.

Observation 1: Only look at the points within distance $\delta$ from L.

Notice that this can still be O(n^2), as if all the points are within distance $\delta$ from L. Which is quite likely.

Magic!

1. Sort S by y coordinate
2. Compute the distance of each point in S with the next 11 points in the sorted order
3. If a pair $q\in Q, r\in R$, with $dist(q, r)< \delta$ is found, return it, and that is the closest such pair

How does this work?

• Divide S into squares of side length delta/2 Observation:

1. Each square has at most 1 point from P
   • The biggest distance between two points is the length of the diagonal of the square
2. If s and s' are more than 11 positions apart in the y sorting order, they are separated by at least rwo of squares.
   • dist(s, s') >= \delta

Time complexity analysis

Recurrence: $T(n) = 2T(n/2) + O(n \log n)$

• By Master Theorem: $O(n log(n)^2)$

Improvement: sort by each coordinate once, and Recurse