# Closest Pair of Points: QuickCP termination check

In A Simple Yet Fast Algorithm for the Closest-Pair Problem Using Sorted Projections on Multi-Dimensions, Mehmet E. Dalkılıç and Serkan Ergun present algorithm QuickCP for finding the closest pair, discussing the planar case more often than other Multi-Dimensions.

#### Algoritm 1 $$\text{QuickCP}(P)$$

// $$P = \{P_1, P_2, \dots , P_n\}$$ where $$P_i = (c₁_i,c₂_i,\dots,c_{ki})$$ i.e., $$n$$ input points in $$k$$ dimensions
for d = 1 to k do // for every dimension d
$$A(d) \leftarrow sortByDimension_d(P)$$ // Sort P by x(y …)-values, store in $$A(d) (A$$scending) i.e.,
$${A(d)(1), A(d)(2), \dots , A(d)(n)}$$
end for
$$d_{min} \leftarrow \infty$$
for r = 1 to n-1 do   // at most n-1 rounds
for d = 1 to k do   // for every dimension d
$$\Delta{_{min}}(d) \leftarrow \infty$$
for i = 1 to n - r do
$$\Delta{_d} \leftarrow A(d)(i+r)\text .d - A(d)(i)\text .d$$   // A(j).d is the value of A(j) in dimension d
$$\Delta{_{min}}(d) \leftarrow min(\Delta{_{min}}(d), \Delta{_d})$$
$$distance \leftarrow$$ Eucledian distance between $$A(d)(i+r) \text{ and } A(d)(i)$$
$$d_{min} \leftarrow min(d_{min}, distance)$$
end for
end for
if $$d_{min} \lt \displaystyle{\sqrt {\sum_d (\Delta{_{min}}(d))^2 }}$$ then
break   // Termination Condition
end if
end for

As presented in the paper named, the termination condition is checked at the end of every iteration through all the dimensions. Initialising $$\Delta{_{min}}(d) \leftarrow 0$$,

Is it correct to instead apply it for each dimension individually/after each inner loop?

• Yes, that should indeed be the case. The termination test checks whether it is farther away than the optimal pair, and if it's already farther away using the projection of a subset of the dimensions, it has to be further away in the full space. I would be surprised if the authors didn't already try this optimization; why don't you try it? Nov 3, 2022 at 11:16
• You can implement the algorithm and submit it as a solution for Closest Pair (Uniform)@kattis.com and Closest [email protected]. Nov 3, 2022 at 11:17