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

Suggested languages for you:

Americas

Europe

Q25E

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 Example${12}$ for finding the closest pair of points, using the Euclidean distance between points, to find the closest pair of the points${\left(}{1}{,}{2}{\right)}{,}{\left(}{1}{,}{6}{\right)}{,}{\left(}{2}{,}{4}{\right)}{,}{\left(}{2}{,}{8}{\right)}{,}{\left(}{3}{,}{1}{\right)}{,}{\left(}{3}{,}{6}{\right)}{,}{\left(}{3}{,}{10}{\right)}{,}{\left(}{4}{,}{3}{\right)}{,}{\left(}{5}{,}{1}{\right)}{,}{\left(}{5}{,}{5}{\right)}{,}{\left(}{5}{,}{9}{\right)}{,}{\left(}{6}{,}{7}{\right)}{,}{\left(}{7}{,}{1}{\right)}{,}{\left(}{7}{,}{4}{\right)}{,}{\left(}{7}{,}{9}{\right)}$and ${\left(}{8}{,}{6}{\right)}$.

The minimum distance of $\sqrt{2}$ between $B$ and $F$.

See the step by step solution

Step 1: Given expression

Given points are:

$\left(1,2\right),\left(1,6\right),\left(2,4\right),\left(2,8\right),\left(3,1\right),\left(3,6\right),\left(3,10\right),\left(4,3\right),\left(5,1\right),\left(5,5\right),\left(5,9\right),\left(6,7\right),\left(7,1\right),\left(7,4\right),\left(7,9\right),\left(8,6\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:

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

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

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

${n}{=}{n}$-space

Step 3: Sort the points in increasing order and plot them on a graph

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

$A=\left(1,2\right)$,$B=\left(1,6\right)$,$C=\left(2,4\right)$,$D=\left(2,8\right)$,$E=\left(3,1\right)$,$F=\left(3,6\right)$,$G=\left(3,10\right)$,$H=\left(4,3\right)$

$I=\left(5,1\right)$,$J=\left(5,5\right)$,$K=\left(5,9\right)$,$L=\left(6,7\right)$,$M=\left(7,1\right)$,$N=\left(7,4\right)$,$O=\left(7,9\right)$,$P=\left(8,6\right)$

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

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

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.

localid="1668578491443" $Dis\left(A,B\right)=\sqrt{{\left(1-1\right)}^{2}+{\left(6-2\right)}^{2}}$

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

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

Similarly, $Dis\left(C,D\right)=4, Dis\left(E,F\right)=5, Dis\left(G,H\right)=5\sqrt{2}, Dis\left(I,J\right)=4$

$Dis\left(K,L\right)=\sqrt{5}, Dis\left(M,N\right)=3, Dis\left(O,P\right)=\sqrt{10}$

Next, compute the minimum distance among the lists.

$\left\{A,B,C,D\right\},\left\{E,F,G,H\right\},\left\{I,J,K,L\right\},\left\{M,N,O,P\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.

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

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

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

$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 $H$ are the points that are closest together, with one point in each sublist.

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

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

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

$Dis\left(I,J,K,L\right)=\mathrm{min}Dis\left(I,J\right),Dis\left(K,L\right),Dis$(Elements of both lists))

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

$Dis\left(I,J,K,L\right)=\mathrm{min}\left(4,\sqrt{5},\sqrt{{\left(6-5\right)}^{2}+{\left(7-5\right)}^{2}}\right)$

$Dis\left(I,J,K,L\right)=\mathrm{min}\left(4,\sqrt{5},\sqrt{5}\right)$

$Dis\left(I,J,K,L\right)=\sqrt{5}$

localid="1668589518830" $Dis\left(M,N,O,P\right)=\mathrm{min}Dis\left(M,N\right),Dis\left(O,P\right),Dis$(Elements of both lists))

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

$Dis\left(M,N,O,P\right)=\mathrm{min}\left(3,\sqrt{10},\sqrt{{\left(8-7\right)}^{2}+{\left(6-4\right)}^{2}}\right)$

$Dis\left(M,N,O,P\right)=\mathrm{min}\left(3,\sqrt{10},\sqrt{5}\right)$

$Dis\left(M,N,O,P\right)=\sqrt{5}$

Step 5: Compute the minimum distance and find

Compute the minimum distance among the lists.

$\left\{A,B,C,D,E,F,G,H\right\},\left\{I,J,K,L,M,N,O,P\right\}$

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

The line separates the points in the two sub-lists are $x=4.5$.

role="math" localid="1668590936318" $d=\mathrm{min}\left(Dis\left(A,B,C,D\right),Dis\left(E,F,G,H\right)\right)$

$d=\mathrm{min}\left(\sqrt{5},\sqrt{5}\right)$

$d=\sqrt{5}$

Now, only need to check the distance between the points with $x$-coordinates in $\left(4.5-\sqrt{5},4.5-\sqrt{5}\right)$ which are all points while the $y$-coordinates can differ by at most $d=\sqrt{5}$

While the pair $BF$ has the shortest distance,

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

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

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

Step 6: Find the minimum distance in the total list

$Dis\left(I,J,K,L,M,N,O,P\right)=\mathrm{min}\left(Dis\left(I,J,K,L\right),Dis\left(M,N,O,P\right),Dis$(Elements of both lists)

Finally, compute the minimum distance in the total list.

$Dis\left(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P\right)=\mathrm{min}\left(Dis\left(A,B,C,D,E,F,G,H\right),Dis\left(I,J,K,L,M,N,O,P\right),Dis$ (Elements of both lists)

$Dis\left(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P\right)=2$

Recommended explanations on Math Textbooks

94% of StudySmarter users get better grades.