• :00Days
• :00Hours
• :00Mins
• 00Seconds
A new era for learning is coming soon

Suggested languages for you:

Americas

Europe

Q24E

Expert-verified
Found in: Page 536

### Discrete Mathematics and its Applications

Book edition 7th
Author(s) Kenneth H. Rosen
Pages 808 pages
ISBN 9780073383095

# Apply the algorithm described in the Example $\mathbf{12}$for finding the closest pair of points, using the Euclidean distance between points, to find the closest pair of the points$\mathbf{\left(}\mathbf{1}\mathbf{,}\mathbf{3}\mathbf{\right)}\mathbf{,}\mathbf{\left(}\mathbf{1}\mathbf{,}\mathbf{7}\mathbf{\right)}\mathbf{,}\mathbf{\left(}\mathbf{2}\mathbf{,}\mathbf{4}\mathbf{\right)}\mathbf{,}\mathbf{\left(}\mathbf{2}\mathbf{,}\mathbf{9}\mathbf{\right)}\mathbf{,}\mathbf{\left(}\mathbf{3}\mathbf{,}\mathbf{1}\mathbf{\right)}\mathbf{,}\mathbf{\left(}\mathbf{3}\mathbf{,}\mathbf{5}\mathbf{\right)}\mathbf{,}\mathbf{\left(}\mathbf{4}\mathbf{,}\mathbf{3}\mathbf{\right)}$and ${\mathbf{\left(}}{\mathbf{4}}{\mathbf{,}}{\mathbf{7}}{\mathbf{\right)}}$.

The required distance between $A$and $C$is $\sqrt{2}$.

See the step by step solution

## Step 1: Given Information

Given points are:

$\left(1,3\right),\left(1,7\right),\left(2,4\right),\left(2,9\right),\left(3,1\right),\left(3,5\right),\left(4,3\right),\left(4,7\right)$

## Step 2: Definition of Euclidean distance

In mathematics, the Euclidean distance between two points in Euclidean space is the length of a line segment between the two points.

Formula:

${\mathbit{d}}{\mathbf{\left(}}{\mathbf{p}}{\mathbf{,}}{\mathbf{q}}{\mathbf{\right)}}{\mathbf{=}}\sqrt{\mathbf{\sum }_{\mathbf{i}\mathbf{=}\mathbf{1}}^{\mathbf{n}}{\mathbf{\left(}{\mathbf{q}}_{\mathbf{i}}\mathbf{-}{\mathbf{p}}_{\mathbf{i}}\mathbf{\right)}}^{\mathbf{2}}}$

${\mathbit{p}}{\mathbf{,}}{\mathbit{q}}{\mathbf{}}{\mathbf{=}}{\mathbf{}}$Two points in Euclidean n-space

${{\mathbit{q}}}_{{\mathbf{i}}}{\mathbf{,}}{{\mathbit{p}}}_{{\mathbf{i}}}{\mathbf{=}}$Euclidean vectors, starting from the origin of the space (initial point)

${\mathbit{n}}{\mathbf{}}{\mathbf{=}}{\mathbf{}}{\mathbit{n}}$-space

## Step 3: Determine the closest pair of the given point by the Euclidean distance formula

Sort the points in increasing order of the $x$-coordinates:

$\begin{array}{l}A=\left(1,3\right), B=\left(1,7\right)\\ C=\left(2,4\right), D=\left(2,9\right)\\ E=\left(3,1\right), F=\left(3,5\right)\\ G=\left(4,3\right), H=\left(4,7\right)\end{array}$

Divide the list into sub-lists until it obtains sub-lists of two elements each.

$\begin{array}{l}\left\{A,B,C,D\right\},\left\{E,F,G,H\right\}\\ \left\{A,B\right\},\left\{C,D\right\},\left\{E,F\right\},\left\{G,H\right\}\end{array}$

Distance formula:

$d\left(\left({x}_{1},{y}_{1}\right),\left({x}_{2},{y}_{2}\right)\right)=\sqrt{{\left({x}_{2}-{x}_{1}\right)}^{2}+{\left({y}_{2}-{y}_{1}\right)}^{2}}$

When the list contains $n=2$ elements, then the distance "Dis" between the two points is the minimum distance.

$Dis\left(A,B\right)=\sqrt{{\left(1-1\right)}^{2}+{\left(7-3\right)}^{2}}$

$Dis\left(A,B\right)=\sqrt{16}$

$Dis\left(A,B\right)=4$

Similarly,localid="1668594250851" $Dis\left(C,D\right)=5, Dis\left(E,F\right)=4, Dis\left(G,H\right)=4.$

## Step 4: Simplify further to find Dis(A,B,C,D,E,F,G,H)

Next, compute the minimum distance among the lists $\left\{A,B,C,D\right\},\left\{E,F,G,H\right\}$

$Dis\left(A,B,C,D\right)=\mathrm{min}\left(Dis\left(A,B\right),Dis\left(C,D\right),Dis$(Elements of both lists))

$A$ and $C$ are the points that are closest together, with one point in each sublist.

$Dis\left(A,B,C,D\right)=\mathrm{min}\left(4,5,\sqrt{{\left(2-1\right)}^{2}+{\left(4-3\right)}^{2}}\right)$

$Dis\left(A,B,C,D\right)=\mathrm{min}\left(4,5,\sqrt{2}\right)$

$Dis\left(A,B,C,D\right)=\sqrt{2}$

localid="1668600861769" $Dis\left(E,F,G,H\right)=\mathrm{min}\left(Dis\left(E,F\right),Dis\left(G,H\right),Dis$(Elements of both lists))

$E$ and $G$ are the points that are closest together, with one point in each sublist.

Note: $F$and$G$, and$F$and$H$ are at the same distance.

$Dis\left(E,F,G,H\right)=\mathrm{min}\left(4,4,\sqrt{{\left(4-3\right)}^{2}+{\left(3-1\right)}^{2}}\right)$

$Dis\left(E,F,G,H\right)=\mathrm{min}\left(4,5,\sqrt{5}\right)$

$Dis\left(E,F,G,H\right)=\sqrt{5}$

Finally, compute the minimum distance in the total list.

$Dis\left(A,B,C,D,E,F,G,H\right)$=min$\left(Dis\left(A,B,C,D\right)$,$Dis\left(E,F,G,H\right)$,$Dis\left(elementsofbothlists\right)\right)$

The average of the $X$-coordinate is$2.5.$

$d=Min\left(Dis\left(A,B,C,D\right),Dis\left(E,F,G,H\right)\right)$

$d=$Min$\left(\sqrt{2},\sqrt{5}\right)$

$d = \sqrt{2}$

Now, only need to check the distance between the points.

$X$-coordinate in$\left(2.5-\sqrt{2},2.5-\sqrt{2}\right)$which are the points$C$,$D$,$E$, $F$

While the$Y$-coordinates can differ by at most$d=\sqrt{2}$.

While the pair$C$$F$has the shortest distance.

$Dis\left(A,B,C,D,E,F,G,H\right)=\mathrm{min}\left(\sqrt{2},\sqrt{5},\sqrt{{\left(3-2\right)}^{2}+{\left(5-4\right)}^{2}}\right)$

$Dis\left(A,B,C,D,E,F,G,H\right)=\mathrm{min}\left(\sqrt{2},\sqrt{5},\sqrt{2}\right)$

$Dis\left(A,B,C,D,E,F,G,H\right)=\sqrt{2}$

## Step 5: Plot the given points on the graph

While it obtained the minimum distance of $\sqrt{2}$ between points $A$ and$C\left(seeDis\right\}\left(A,B,C,D\right)\right).$