The Closest Pair of Factors drawback is a typical matter in an algorithms course at the moment, however after I taught such a course fifty years in the past, the algorithm was not but identified.

### Contents

#### California Dreaming

Think about you might be driving a automotive on the Harbor Freeway in southern California with typical Los Angeles visitors situations. Among the many many stuff you would possibly wish to know is which pair of autos is nearest one another.

That is an occasion of the Closest Pair of Factors drawback:

- Given the situation of
`n`factors within the aircraft, which pair of factors is closest to one another?

#### Closest Pair of Factors

It’s handy to symbolize the factors by a vector of advanced values. The gap between factors `z(ok)` and `z(j)` is then

d = abs(z(ok) - z(j))

Listed here are a couple of factors within the unit sq.. The closest pair is highlighted.

`Pairs`

The primary algorithm you would possibly consider computes the space between all attainable pairs of factors and finds the minimal. This can be a brute power strategy that requires just a few strains of code.

perform d = Pairs(z) % Pairs. % d = Pairs(z) is the minimal distance between any two parts % of the advanced vector z.

n = size(z); d = Inf; for ok = 1:n for j = ok+1:n if abs(z(ok) - z(j)) < d d = abs(z(ok) - z(j)); finish finish finish finish

`DivCon`

DivCon stands for Divide and Conquer. In define, the steps are:

- Divide the set of factors into two halves.

- Recursively, discover the closest pair in every half.

- Think about the case when the closest pair has one level in every half.

- Terminate the recursion with units of two or three factors.

perform d = DivCon(z,sorted) % DivCon. % d = DivCon(z) is the minimal distance between any two parts % of the advanced vector z. % % d = DivCon(z,true) is a recursive name with ascending actual(z).

n = size(z); if n <= 3 d = Pairs(z); else if nargin < 2 || ~sorted [~,p] = type(actual(z)); z = z(p); finish m = ground(n/2);

% Left half dl = DivCon(z(1:m),true)

% Proper half dr = DivCon(z(m+1:finish),true);

% Select d = min(dl,dr);

% Middle strip ds = Middle(z,d); d = min(ds,d); finish finish

`Middle`

The fragile case entails the strip of factors close to the middle dividing line. The width of the strip is the closest distance discovered within the recursion. Any nearer pair with one level in every half have to be on this strip.

perform d = Middle(z,d) % Middle(z,d) is utilized by DivCon to look at the % strip of half-width d concerning the heart level.

n = size(z) m = ground(n/2); xh = actual(z(m)); [~,p] = type(imag(z)); z = z(p); s = []; for i = 1:n if abs(actual(z(i)) - xh) < d s = [s; z(i)]; finish finish

ns = size(s); for ok = 1:ns for j = ok+1:ns if (imag(s(j)) - imag(s(ok))) < d && abs(s(ok) - s(j)) < d d = abs(s(ok) - s(j)); finish finish finish finish

#### Complexity

Let `n` be the variety of factors. An asymptotic execution-time complexity evaluation entails `n` approaching infinity.

It’s not onerous to see that the complexity of the brute power algorithm carried out in `Pairs` is O(`n`^2).

There are dozens of pages on the internet dedicated to exhibiting that the complexity of the divide and conquer algorithm carried out in `DivCon` and `Middle` is O(`n`*log(`n`)). The most effective web page that I’ve seen is the YouTube video by Ling Qi. The important thing to the evaluation is exhibiting that the interior loop in `Middle` is executed at most 7 instances for any `n`.

#### Timing

We measured the execution time of `Pairs(z)` and `DivCon(z)` for `n` from 1,000 to 40,000 and computed the ratios of the 2 instances. The complexity evaluation predicts that this ratio is asymptotically

O(n/log(n))

Listed here are the timing outcomes and a least sq. match by `n`/log(`n`).

#### Software program

A self-extracting MATLAB archive is out there at https://blogs.mathworks.com/cleve/information/TestDivCon_mzip.m

#### References

Ling Qi, IDeer7, *Closest Pair of Factors (Divide and Conquer) Defined*. https://www.youtube.com/watch?v=6u_hWxbOc7E.

Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford. *Introduction to Algorithms (4th ed.)*. MIT Press and McGraw-Hill. ISBN 0-262-04630-X. 1312 pp.

Printed with MATLAB® R2023a