The closest$-$pair problem calls for finding the two closest points in a set of n

points. It is the simplest of a variety of problems in computational geometry that

deals with proximity of points in the plane or higher$-$dimensional spaces. Points

in question can represent such physical objects as airplanes or post offices as well

as database records, statistical samples, DNA sequences, and so on$.$ An air$-$traffic

controller might be interested in two closest planes as the most probable collision

candidates. A regional postal service manager might need a solution to the closest$-$

pair problem to find candidate post$-$office locations to be closed.

One of the important applications of the closest$-$pair problem is cluster analy$-$

sis in statistics. Based on n data points, hierarchical cluster analysis seeks to orga$-$

nize them in a hierarchy of clusters based on some similarity metric. For numerical

data, this metric is usually the Euclidean distance; for text and other nonnumerical

data, metrics such as the Hamming distance $($see Problem $5$ in this section$$s ex$-$

ercises$)$ are used. A bottom$-$up algorithm begins with each element as a separate

cluster and merges them into successively larger clusters by combining the closest

pair of clusters.

For simplicity, we consider the two$-$dimensional case of the closest$-$pair prob$-$

lem. We assume that the points in question are specified in a standard fashion by

their $($x$,$ y$)$ Cartesian coordinates and that the distance between two points p i $($x i $,$

yi $)$ and p j $($xj $,$ y j $)$ is the standard Euclidean distance

d$($p i $,$ p j $)=$

$$

$($x i $$ xj $)2+($y i $$ y j $)2.$

The brute$-$force approach to solving this problem leads to the following ob$-$

vious algorithm: compute the distance between each pair of distinct points and

find a pair with the smallest distance. Of course, we do not want to compute the

distance between the same pair of points twice. To avoid doing so$,$ we consider

only the pairs of points $($p i $,$ p j $)$ for which i $$ j $.$

$3\mathrm{.}3$ Closest$-$Pair and Convex$-$Hull Problems by Brute Force $109$

Pseudocode below computes the distance between the two closest points;

getting the closest points themselves requires just a trivial modification.

ALGORITHM BruteForceClosestPair$($P $)$

$//$Finds distance between two closest points in the plane by brute force

$//$Input: A list P of n $($n $>=2)$ points p$1($x$1,$ y$1),...,$ pn $($xn $,$ yn $)$

$//$Output: The distance between the closest pair of points

d $\backslash$infty

for i $1$ to n $1$ do

for j $$ i $+1$ to n do

d $$ min$($d$,$ sqrt$(($x i $$ x j $)2+($y i $$ yj $)2))//$sqrt is square root

return d

Can you design a more efficient algorithm than the one based on the brute$-$

force strategy to solve the closest$-$pair problem for $n$ points $x_1,x_2,$dots,$x_n$ on

the real lines?solution in the form of pseudo code