The divide-and-conquer algorithm

We need to find the closest pair of points in a set $Q$ of $n\ge 2$ points. Brute force will take $\Theta(n^2)$ time.

Each recursive call takes as input a subset $P\subseteq Q$ and arrays $Z$ and $Y$ each of which contains all the points o fhte input subset $P$. Points in $X$ are sorted on their $x$-coordinates monotonically increasing and $Y$ is sorted on monotonically increasing $y$-coordindate.

If $\vert P\vert\le 3$ we use brute force method otherwise:

• Divide: Find a vertical line $l$ that bisects the point set $P$ intro two sets $P_L$ and $P_R$ such that $\vert P_L\vert =\lceil \vert P\vert /2\rceil$, $\vert P_R\vert =\lfloor \vert P\vert /2\rfloor$. Divide $X$ into $X_L$ and $X_R$. Similarly $Y$ into $Y_L$ and $Y_R$.
• Conquer: Make two recursive calls one in $P_L$ and other one $P_R$ for closest pair of point. Let the closest-pair distances returned be $\delta_L$ and $\delta_R$ respectively and let $\delta=\min(\delta_L, \delta_R)$
• Combine: The closest pair is either (i) the pair with $\delta$ or (ii) a pair of point with one in $P_L$ and one in $P_R$ whose distance is less than $\delta$
  • Create $Y’$ which is the array $Y$ with all points in $2\delta$-wide vertical strip around $l$
  • For each point $p$ in $Y’$ try to find points in $Y’$ that are withing $\delta$ units of $p$. Only $7$ points in $Y’$ that follow $p$ need to be considered. Compute distance from $p$ to each of these 7 points and keep track of the closest-pair distance $\delta’$ found over all pairs of points in $Y’$.
  • Return pair of point with smallest distance $\delta’$ or $\delta$.

Why only 7 points?

Suppose $p_L\in P_L$ and $p_R\in P_R$ have distance less than $\delta$. $p_L$ and $p_R$ should be individually less than $\delta$ distance from $l$. They are also within $\delta$ distance of each other vertically. So they must be in $\delta\times 2\delta$ rectangle as shown.

Consider a $\delta\times\delta$ square forming the left half of a $\delta\times 2\delta$ rectangle, since all points withing $P_L$ are atleast $\delta$ apart, atmost 4 points in $P_R$ can reside withing the $\delta\times \delta$ square. Similarly 4 for right side and total 8 points.

Therefore we need to only check next 7 points.

Time Complexity

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