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?
