Question

In this problem we will develop a divide-and-conquer algorithm for the following geometric task.

CLOSEST PAIRInput: A set of points in the plane, $\left\{p_1=(x_1;y_1),p_2=(x_2,y_2),...,p_n=(x_n,y_n)\right\}$

Output: The closest pair of points: that is, the pair ${\mathit{P}}_{\mathbf{i}}\mathbf{\ne }{\mathit{P}}_{\mathbf{j}}$for which the distance between ${\mathit{p}}_{\mathbf{i}}$and ${\mathit{p}}_{\mathbf{j}}$, that is,

$\sqrt{{\left(x_i-x_i\right)}^{\mathbf{2}}\mathbf{+}\mathbf{z}{\left(y_i-y_i\right)}^{\mathbf{2}}}$,

is minimized.

For simplicity, assume that n is a power of two, and that all the x-coordinates role="math" localid="1659237354869" ${\mathit{x}}_{\mathit{i}}$ are distinct, as are the y-coordinates.

Here’s a high-level overview of the algorithm:

.Find a value for which exactly half the points have ${\mathit{x}}_{\mathbf{i}}\mathbf{<}\mathit{x}$, and half have ${\mathit{x}}_{\mathbf{i}}\mathbf{>}\mathit{x}$. On this basis, split the points into two groups, L and R.

• Recursively find the closest pair in L and in R. Say these pairs are ${\mathit{p}}_{\mathbf{L}}\mathbf{·}{\mathit{q}}_{\mathbf{L}}\mathbf{\in }\mathit{L}$and ${\mathit{p}}_{\mathbf{R}}\mathbf{·}{\mathit{q}}_{\mathbf{R}}\mathbf{\in }\mathit{R}$with distances ${\mathit{d}}_{\mathbf{L}}$and ${\mathit{d}}_{\mathbf{R}}$ respectively. Let d be the smaller of these two distances.

• It remains to be seen whether there is a point in Land a point in R that are less than distance dapart from each other. To this end, discard all points with ${\mathit{x}}_{\mathbf{i}}\mathbf{<}\mathit{x}\mathbf{-}\mathit{d}$or ${\mathit{x}}_{\mathbf{i}}\mathbf{>}\mathit{x}\mathbf{+}\mathit{d}$ and sort the remaining points by y-coordinate.

• Now, go through this sorted list, and for each point, compute its distance to the seven subsequent points in the list. Let ${\mathit{p}}_{\mathbf{M}}\mathbf{·}{\mathit{q}}_{\mathbf{M}}$be the closest pair found in this way.

• The answer is one of the three pairs role="math" localid="1659237951608" $\mathbf{\{}{\mathbf{p}}_{\mathbf{L}}\mathbf{,}{\mathbf{q}}_{\mathbf{L}}\mathbf{\}}\mathbf{,}\mathbf{\{}{\mathbf{p}}_{\mathbf{R}}\mathbf{,}{\mathbf{q}}_{\mathbf{R}}\mathbf{\}}\left\{p_M,q_M\right\}$, whichever is closest.

(a) In order to prove the correctness of this algorithm, start by showing the following property: any square of size $\mathit{d}\mathbf{\times }\mathit{d}$ in the plane contains at most four points of L.

(b) Now show that the algorithm is correct. The only case which needs careful consideration is when the closest pair is split between L and R.

(c) Write down the pseudocode for the algorithm, and show that its running time is given by the recurrence:

$\mathit{T}\mathbf{\left(}\mathit{n}\mathbf{\right)}\mathbf{=}\mathbf{2}\mathit{T}\mathbf{\left(}\mathit{n}\mathit{l}\mathbf{2}\mathbf{\right)}\mathbf{+}\mathbf{0}\mathbf{\left(}\mathit{n}\mathit{l}\mathit{o}\mathit{g}\mathit{n}\mathbf{\right)}$

Show that the solution to this recurrence is $\mathit{o}\mathbf{(}\mathit{n}\mathbf{}\mathit{l}\mathit{o}{\mathit{g}}^{\mathbf{z}}\mathit{n}\mathbf{)}$.

(d) Can you bring the running time down to $\mathbf{O}\mathbf{(}\mathbf{n}\mathbf{}\mathbf{logn}\mathbf{)}$?

Short answer

(a) The proof is already be given in the solution.

(b) The algorithm stated is correct.

(c) The run time is $o\left(n{\log }^{2}n\right)$.

(c) Yes algorithm can be scale down.

Step-by-step solution

Step – 1: Introduction  

The divide-and-conquer approach is a technique for solving different issues in algorithms. It is a strategy in which the problem is divided into multiple sub-problems.

• After that, each sub-problem is addressed on its own.

• Finally, the outcomes of the sub-problems are combined to provide a final solution.

• To get the nearest pair of points on a plane, a divide-and-conquer approach is applied.

Step – 2: Solution of each part

(a)

Consider the information:

• The points are divided into two parts, the L and the R .

• The goal is to show that L includes no more than four points in any $d\times d$square.

• Assume a square is located on a $d\times d$plane.

• If the square has five or more points, split it into four equal sections.

• The smaller squares are represented by these four sections.

• A pair of points must be found in the same smaller square.

• The distance between two locations in the same smaller square must be at least

$T\left(n\right)=2T\left(nl2\right)+a\left(nlogn\right)$

• This violates the assertion that every pair of points is separated by at least " d ".

As a result, it's determined that a $d\times d$square can only have four points.

The algorithm stated is correct.

(b)

Allow the information:

• The divide-and-conquer algorithm is used to find the closest pair of points.

• The objective is to prove the correctness of the algorithm.

Positive Implementation:

• If the recursion is not bottomed down to a single-point sub-problem, the procedure works appropriately.

• Make sure that the divide-and-conquer method does not result in a sub-problem with only one point while executing the splitting phase.

• Also, from the list, calculating the distance between seven successive spots is adequate.

• It's because a $d\times 2d$rectangle can only hold eight points. Assume that the left rectangle is formed by a $d\times d$square with a maximum of four points.

• Similarly, with at most four points, the $d\times d$square forms the right side of the rectangle.

• As a result, a $d\times 2d$rectangle can only contain points.

• With eight points in the rectangle, it is evident that checking the distances of the next seven points in the list is sufficient.

As a result, the divide-and-conquer method used to solve the issue of determining the nearest pair is accurate

The run time of algorithm.

(c)

Consider the information:

• The objective is to show that the pseudocode of the closest pair algorithm has a recurrence relation $T\left(n\right)=2T\left(nl2\right)+o\left(n\log n\right)$which results in a running time of $o\left(nlo{g}^{2}n\right)$.

Pseudocode:

The pseudocode of the closest pair algorithm has the following steps-

• Finding a line that splits the collection of points into two half L and R is the first stage. The points are saved in the X and Y arrays. xhas been sorting x-coordinates more and more, whereas y has been sorting y-coordinates more and more.

• The needed pair is found in L by one recursive call, and the required pair is found in R by the other recursive call. The least of the two estimated distances determines the final closest pair.

• The closest pair of points is determined among the three pairs of points in the last phase. It might be one of the recursive call's pair of points, or it could be a pair with one point on each side.

Running time:

• In each recursive invocation of the algorithm, the two array inputs are given x and y . x contain x-coordinates and y contain y-coordinates.

• Because the sort is performed at each recursive call, the recurrence relation of the algorithm results in $T\left(n\right)=2T(n⁄2)+O(n\log n)$.

• Using the Master’s theorem, with the above recurrence relation, the algorithm’s running time results in $o\left(nlo{g}^{2}n\right)$.

Therefore, the running time of the closest pair algorithm is $o\left(n{\log }^{2}n\right)$.

The algorithm can be scale down.

(d)

Consider the information:

The aim is to investigate that whether the closest pair problem can be solved in $o\left(n\log n\right)$.

“Yes”, the closest pair problem can be solved in $o\left(n\log n\right)$.

Explanation:

• The running time of the algorithm results in $o\left(n{\log }^{2}n\right)$. Because sorted arrays are being passed in every recursive call.

• The primary goal should be to sort the arrays in the first place. This cuts down on the amount of time it takes to complete the task.

• The sorted arrays can be sent to the first recursive function to accomplish this.

• All subsequent recursive calls will be linearly timed.

• This way the recurrence relation of the algorithm is $T\left(n\right)=2T\left(n/2\right)+o\left(n\right)$.

• This recurrence relation gives a running time of$o\left(n\log n\right)$.

Therefore, the time complexity of $o\left(n\log n\right)$can be achieved by presorting.