Book edition 7th

Author(s) Kenneth H. Rosen

Pages 808 pages

ISBN 9780073383095

Answers without the blur.

Just sign up for free and you're in.

Short Answer

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)$ .

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

See the step by step solution

Step by Step Solution

TABLE OF CONTENTS :

TABLE OF CONTENTS

Step 1: 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)$ .

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 (p, q) = \sqrt{\sum_{i = 1}^{n} {(q_{i} - p_{i})}^{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 = (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.

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

Distance formula: $d ((x_{1}, y_{1}), (x_{2}, y_{2})) = \sqrt{{(x_{2} - x_{1})}^{2} + {(y_{2} - y_{1})}^{2}}$

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

localid="1668578491443" $D i s (A, B) = \sqrt{{(1 - 1)}^{2} + {(6 - 2)}^{2}}$

$D i s (A, B) = \sqrt{16}$

$D i s (A, B) = 4$

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

$D i s (K, L) = \sqrt{5}, D i s (M, N) = 3, D i s (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 (4, 4, \sqrt{{(2 - 1)}^{2} + {(4 - 2)}^{2}})$

$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 (5, 5 \sqrt{2}, \sqrt{{(4 - 3)}^{2} + {(3 - 1)}^{2}})$

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

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

$D i s (I, J, K, L) = \min D i s (I, J), D i s (K, L), D i s$ (Elements of both lists))

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

$D i s (I, J, K, L) = \min (4, \sqrt{5}, \sqrt{{(6 - 5)}^{2} + {(7 - 5)}^{2}})$

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

$D i s (I, J, K, L) = \sqrt{5}$

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

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

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

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

$D i s (M, N, O, P) = \sqrt{5}$

Step 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}$

$D i s (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))$

$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 $B F$ has the shortest distance,

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

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

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

Step 6: 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 (D i s (A, B, C, D, E, F, G, H), Dis (I, J, K, L, M, N, O, P), D i s$ (Elements of both lists)

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

Find Study Materials for

Create Study Materials

Select your language

Discrete Mathematics and its Applications

Answers without the blur.

Short Answer

Step by Step Solution

Step 1: Given expression

Step 2: Definition of Euclidean distance

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

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

Step 5: Compute the minimum distance and find

Step 6: Find the minimum distance in the total list

Most popular questions for Math Textbooks

Want to see more solutions like these?

Recommended explanations on Math Textbooks

Select your language

Discrete Mathematics and its Applications

Answers without the blur.

Short Answer

Apply the algorithm described in Example12 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).

Step by Step Solution

Step 1: Given expression

Step 2: Definition of Euclidean distance

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

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

Step 5: Compute the minimum distance and find

Step 6: Find the minimum distance in the total list

Most popular questions for Math Textbooks

Want to see more solutions like these?

Recommended explanations on Math Textbooks

Decision Maths

Calculus

Probability and Statistics

Statistics

Mechanics Maths

Geometry

Pure Maths