Question

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

$(1,2),(1,6),(2,4),(2,8),(3,1),(3,6),(3,10),(4,3),(5,1),(5,5),(5,9),(6,7),(7,1),(7,4),(7,9)$and $(8,6)$.

Short answer

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

Step-by-step solution

Given expression

Given points are:

$(1,2),(1,6),(2,4),(2,8),(3,1),(3,6),(3,10),(4,3),(5,1),(5,5),(5,9),(6,7),(7,1),(7,4),(7,9),(8,6)$.

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(\mathbf{p},\mathbf{q})=\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

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

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

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

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

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

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(A,B)=\sqrt{{(1-1)}^2+{(6-2)}^2}$

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

$Dis(A,B)=4$

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

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

Next, compute the minimum distance among the lists.

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

$Dis(A,B,C,D)=\min (Dis(A,B),Dis(C,D),Dis$(Elements of both lists)

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

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

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

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

$Dis(E,F,G,H)=\min (Dis(E,F),Dis(G,H),Dis$(Elements of both lists)

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

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

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

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

$Dis(I,J,K,L)=\min Dis(I,J),Dis(K,L),Dis$(Elements of both lists))

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

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

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

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

localid="1668589518830" $Dis(M,N,O,P)=\min Dis(M,N),Dis(O,P),Dis$(Elements of both lists))

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

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

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

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

Compute the minimum distance and find

Compute the minimum distance among the lists.

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

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

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

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

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

$d=\sqrt{5}$

Now, only need to check the distance between the points with $x$-coordinates in $(4.5-\sqrt{5},4.5-\sqrt{5})$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(A,B,C,D,E,F,G,H)=\min \left(\sqrt{5},\sqrt{5},\sqrt{{(3-1)}^2+{(6-6)}^2}\right)$

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

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

Find the minimum distance in the total list

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

Finally, compute the minimum distance in the total list.

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

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