1
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – Pål GD
    Nov 3, 2022 at 11:16
  • $\begingroup$ You can implement the algorithm and submit it as a solution for Closest Pair (Uniform)@kattis.com and Closest [email protected]. $\endgroup$
    – Pål GD
    Nov 3, 2022 at 11:17

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.