Question

Use pseudocode to describe the recursive algorithm for solving the closest-pair problem as described in Example 12.

Short answer

The minimum distance and the closest pair $d$.

Step-by-step solution

Definition of shortest distance

The distance between two array values is the number of indices between them.

Find the closest pair by the formula of shortest distance and midpoint

closest $\left(\right(x_1,y_1),...,(x_n,y_n)$list of points with $n\ge 1)$

If the list contains only two points, then the minimum distance is the distance between the two points and the two closest points are the two points in the list. if $n=2$then,$d=\sqrt{{(x_2-x_1)}^2+{(y_2-y_1)}^2}$

Pair $=\left\{(x_1,y_1),(x_2,y_2)\right\}$

Divide the list into two sub lists and perform the algorithm

Divide the list into two sub lists and perform the algorithm on the sub lists first.

$d$will represent the minimum distance between among the two sub lists.

The minimum is then the minimum $d$and the pair of points with one point in each sub list.

$m$will represent the middle between the $x$-coordinates of the two sub lists and now, only need to check the points that are within $d$of $m$for the pairs across the two sub lists.

$m=\left(x_{\left[n/2\right]}+x_{\left[n/2\right]}\right)/2,d_L$, $Pai{r}_L:=closest\left(\right(x_1,y_1),...,(x_{\left[n/2\right]},y_{\left[n/2\right]}\left)\right)$

$d_R$, pair

If , then $d=d_L$.

$d=d_R$

$P^{\text{'}}=$sub list of points whose $x$-coordinates are within $d$of $m$.

For every point $(x,y)$in $p$

for every point $(x\text{'},y\text{'})$ in $P\text{'}$ after $(x,y)$ such that

$y\text{'}-y<d,a=\sqrt{{(x\text{'}-x)}^2+{(y\text{'}-y)}^2}$

If $a<d$ then$a=\left\{\left(x,y\right),(x\text{'},y\text{'})\right\}$

Finally, the minimum distance and the closest pair. return $d$, pair.