# Closest pair of points in 3D

My professor mentioned that if we already know the divide and conquer algorithm for the closest pair of points in 2 dimensions it's easy to think of a similar algorithm for the 3 dimensions. But I am a bit confused as to what changes we have to make.

I think we'll divide the points in two sets based on the x coordinate, find the closest pair of points in each set (let's say that the minimum distance is δ) but instead of a strip (2δ width), since we have three dimensions we'll use a slab to compare the distance between point that exist in different sets. But I don't know what I have to do next.

As you say, you can split the points in two sets $$A$$ and $$B$$ of roughly the same size, depending on whether their $$x$$ coordinate smaller than or at least some threshold $$x_0$$. Solve the problem recursively on $$A$$ and $$B$$ and let $$\delta$$ be the minimum distance between any two points in the same set.

Now, instead of a strip of width $$2\delta$$, consider a slab with width $$2\delta$$ (centered on $$x_0$$) and with unbounded height and depth (towards the $$y$$ and $$z$$ axes).

Notice that a necessary condition for pair of points $$p_a \in A$$ and $$p_b \in B$$ to be at distance less than $$\delta$$ is that both $$p_a$$ and $$p_b$$ must belong to the slab.

Imagine subdividing this slab into cubes having side $$\delta/2$$, so that no cube crosses $$x_0$$. Pick any point $$p$$ in the slab and consider the "supercube" $$C_p$$ of side $$2\delta$$ centered in $$p$$. All points outside of $$C_p$$ are either outside of the slab or are too far away from $$p$$ even when we just consider the difference of the $$y$$ or $$z$$ coordinates. The means that, if there is a point at distance at most $$\delta$$ from $$p$$, then it must belong to $$C_p$$. However $$C_p$$ intersects at most $$5^3$$ cubes. This means that for each point we only need to check the points in at most $$5^3$$ cubes.

How many points are there in these cubes? At most $$5^3$$. To see this notice that a cube cannot contain more than one point. Indeed, each cube is entirely contained in either $$A$$ or $$B$$ and the maximum distance between two points in the same cube is $$\frac{\delta}{2} \cdot \sqrt{3} < \delta$$.

How do we check these points efficiently? Let's start with an observation: given a collection $$S$$ of points and some parameter $$\delta$$ with the guarantee that each points has at most constantly many points within distance $$\delta$$, the 2D-algorithm that you already know can be used to enumerate all pairs of points at distance at most $$\delta$$ in time $$O(|S| \log |S|)$$.

Take all the points in the slab and project them onto the 2d-plane perpendicular to the $$x$$ axis and passing through $$x_0$$ (i.e., "squish the slab" along the $$x$$ axis). We only need to consider the pairs of points whose projections are at distance at most $$\delta$$. By the above argument, for each point there are there are at most $$5^3$$ other points within such distance.

But then we can use the 2D-algorithm to get a list of all pairs of points to check! This takes time $$O(|S| \log |S|)$$ where $$|S|$$ is the number of points in the slab. Let's be pessimistic and assume that all current points end up in the slab. We have the following recurrence equation, where $$n$$ denotes the number of points: $$T(n) = 2T(n/2) + O(n \log n),$$ which has solution $$T(n) = O(n \log^2 n)$$ as you can see using the master theorem.

It turns out that you can be more clever in the selection of $$x_0$$. You can pick, in time $$O(n)$$, a threshold that (i) splits the point in $$A$$ and $$B$$ such that $$\min\{|A|, |B|\} \ge c n$$ for some constant $$c>0$$, and (ii) ensures that $$S$$ contains $$O(n^{1-\epsilon})$$ points for some constant $$\epsilon>0$$. With this clever selection you get the following recurrence: \begin{align*} T(n) &\le T(cn) + T((1-c)n) + O(n) + O(n^{1-\epsilon} \log n^{1-\epsilon}) \\ & \le T(cn) + T((1-c)n) + O(n). \end{align*} This recurrence has solution $$T(n) = O(n \log n)$$. To see this you can notice that the recursion tree has depth $$O(\log n)$$ and that the overall time spent on the recursive calls on each level of the tree is $$O(n)$$.

See this paper for an explanation of how to select $$x_0$$.

• And the complexity here remains $O(nlogn)$? Can you explain to me how?
– Hjm
Nov 9, 2022 at 6:59
• @Battle. I've added an explanation to the answer. Nov 9, 2022 at 9:51

The 2D approach you know probably uses sorting. Here I describe how to do it without sorting. This approach is straightforward to generalize to higher dimensions.

Below, "$$\delta$$-close" means "the distance is at most $$\delta$$"

We divided the points based on the $$x$$-coordinate, found $$\delta$$, and now it remains to do the "merge" part. We consider the points that are $$\delta$$-close to the border. Several observations:

1. If $$(x_1,y_1)$$ and $$(x_2,y_2)$$ are $$\delta$$-close, then we have $$|y_1 - y_2| \le \delta$$.
2. For an integer $$k$$, let $$S_k = \{(x,y) \mid y \in [k, k+2] \text{ and (x,y) is \delta-close to the border}\}$$. If $$(x_1,y_1)$$ and $$(x_2,y_2)$$ are $$\delta$$-close, then, by Observation 1, there exists an integer $$k$$ such that both $$(x_1,y_1) \in S_k$$ and $$(x_2,y_2) \in S_k$$.
3. For any $$k$$, $$|S_k|$$ is at most constant.

As a result, we have at most $$O(n)$$ non-empty $$S_k$$. By Observation 2, it suffices for each non-empty $$k$$ to try all possible pairs of points from $$S_k$$, which, by Observation 3, takes constant time.

• So what is the complexity of your algorithm? Is it linear?
– Hjm
Nov 9, 2022 at 8:04
• @Battle. There is a lower bound of $\Omega(n \log n)$ for this problem, where $n$ is the number of points. Nov 9, 2022 at 8:40