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

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

See the step by step solution

Step by Step Solution

TABLE OF CONTENTS :

TABLE OF CONTENTS

Step 1: Given Information

Given points are:

$(1, 3), (1, 7), (2, 4), (2, 9), (3, 1), (3, 5), (4, 3), (4, 7)$

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: 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 = (1, 3), B = (1, 7) \\ C = (2, 4), D = (2, 9) \\ E = (3, 1), F = (3, 5) \\ G = (4, 3), H = (4, 7) \end{array}$

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

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

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.

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

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

$Dis (A, B) = 4$

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

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

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

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

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

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

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

localid="1668600861769" $Dis (E, F, G, H) = \min (Dis (E, F), Dis (G, H), 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 (E, F, G, H) = \min (4, 4, \sqrt{{(4 - 3)}^{2} + {(3 - 1)}^{2}})$

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

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

Finally, compute the minimum distance in the total list.

$D i s (A, B, C, D, E, F, G, H)$ =min $(D i s (A, B, C, D)$ , $D i s (E, F, G, H)$ , $D i s (e l e m e n t s o f b o t h l i s t s))$

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

$d = M i n (D i s (A, B, C, D), D i s (E, F, G, H))$

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

$d = \sqrt{2}$

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

$X$ -coordinate in $(2.5 - \sqrt{2}, 2.5 - \sqrt{2})$ 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.

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

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

$D i s (A, B, C, D, E, F, G, H) = \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 (s e e D i s} (A, B, C, D)) .$

Find Study Materials for

Create Study Materials

Select your language

Discrete Mathematics and its Applications

Answers without the blur.

Short Answer

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

Step by Step Solution

Step 1: Given Information

Step 2: Definition of Euclidean distance

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

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

Step 5: Plot the given points on the graph

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 the Example 12for finding the closest pair of points, using the Euclidean distance between points, to find the closest pair of the points(1,3),(1,7),(2,4),(2,9),(3,1),(3,5),(4,3)and (4,7).

Step by Step Solution

Step 1: Given Information

Step 2: Definition of Euclidean distance

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

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

Step 5: Plot the given points on the graph

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

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