In this section, we discuss more sophisticated and asymptotically more efficient algorithms for these problems, which are based on the divide-and-conquer technique.

** ****The Closest-Pair and Convex-Hull Problems by Divide-and-Conquer**

In previews Section , we discussed the brute-force approach to solving two classic prob-lems of computational geometry: the closest-pair problem and the convex-hull problem. We saw that the two-dimensional versions of these problems can be solved by brute-force algorithms in ** (n**2

**The
Closest-Pair Problem**

Let ** P** be a set of

If 2 ≤ ** n** ≤ 3

recursively
for subsets ** P_{l}** and

Note that
** d** is not necessarily the smallest
distance between all the point pairs because points of a closer pair can lie on
the opposite sides of the separating line. Therefore, as a step combining the
solutions to the smaller subproblems, we need to examine such points.
Obviously, we can limit our attention to the points inside the symmetric
vertical strip of width 2

Let ** S** be the list of points inside the
strip of width 2

subsequently
*d*_{min} ≤ ** d.** Let

cally,
this means that ** p** must
belong to the rectangle shown in Figure 5.7b. The principal insight exploited
by the algorithm is the observation that the rectangle can contain just a few
such points, because the points in each half (left and right) of the rectangle
must be at least distance

Here is
pseudocode of the algorithm. We follow the advice given in Section 3.3 to avoid
computing square roots inside the innermost loop of the algorithm.

**ALGORITHM** *EfficientClosestPair**(P , Q)*

//Solves
the closest-pair problem by divide-and-conquer

//Input:
An array ** P** of

nondecreasing order of their ** x** coordinates and an array

same points sorted in nondecreasing order of the ** y** coordinates //Output: Euclidean
distance between the closest pair of points

**if ***n*** **≤** **3

return
the minimal distance found by the brute-force algorithm

**else**

copy the
first ** n/**2 points of

** d_{r} **←

** d **←min{

** m **←

copy all
the points of ** Q** for
which |

**for ***i*** **←** **0** to ***num*** **−** **2** do **** k **←

**while ***k*** **≤** ***num*** **−** **1** and **** (S**[

** dminsq **←

**return ***sqrt**(dminsq)*

The
algorithm spends linear time both for dividing the problem into two problems
half the size and combining the obtained solutions. Therefore, assuming as
usual that ** n** is a power of 2, we have the
following recurrence for the running time of the algorithm:

** T (n) **=

where ** f (n)** ∈

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

Introduction to the Design and Analysis of Algorithms : Divide and Conquer : The Closest Pair Problem by Divide and Conquer |

**Related Topics **

Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

Copyright © 2018-2024 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.