In this section, we consider a straightforward approach to two well-known prob-lems dealing with a finite set of points in the plane. These problems, aside from their theoretical interest, arise in two important applied areas: computational ge-ometry and operations research.

**Closest-Pair
and Convex-Hull Problems ****by Brute Force**

In this
section, we consider a straightforward approach to two well-known prob-lems
dealing with a finite set of points in the plane. These problems, aside from
their theoretical interest, arise in two important applied areas: computational
ge-ometry and operations research.

The
closest-pair problem calls for finding the two closest points in a set of ** n** points. It is the simplest of a
variety of problems in computational geometry that deals with proximity of
points in the plane or higher-dimensional spaces. Points in question can
represent such physical objects as airplanes or post offices as well as
database records, statistical samples, DNA sequences, and so on. An air-traffic
controller might be interested in two closest planes as the most probable
collision candidates. A regional postal service manager might need a solution
to the closest-pair problem to find candidate post-office locations to be
closed.

One of
the important applications of the closest-pair problem is cluster analy-sis in
statistics. Based on ** n** data
points, hierarchical cluster analysis seeks to orga-nize them in a hierarchy of
clusters based on some similarity metric. For numerical data, this metric is
usually the Euclidean distance; for text and other nonnumerical data, metrics
such as the Hamming distance (see Problem 5 in this section’s ex-ercises) are used.
A bottom-up algorithm begins with each element as a separate cluster and merges
them into successively larger clusters by combining the closest pair of
clusters.

For
simplicity, we consider the two-dimensional case of the closest-pair prob-lem.
We assume that the points in question are specified in a standard fashion by
their ** (x, y)** Cartesian coordinates and that
the distance between two points

The
brute-force approach to solving this problem leads to the following ob-vious
algorithm: compute the distance between each pair of distinct points and find a
pair with the smallest distance. Of course, we do not want to compute the
distance between the same pair of points twice. To avoid doing so, we consider
only the pairs of points *(p _{i},
p_{j}*

** Closest-Pair and Convex-Hull Problems by
Brute Force**

Pseudocode
below computes the distance between the two closest points; getting the closest
points themselves requires just a trivial modification.

**ALGORITHM** *BruteForceClosestPair**(P )*

//Finds
distance between two closest points in the plane by brute force

//Input:
A list ** P** of

** d **←
∞

**for ***i*** **←** **1** to ***n*** **−** **1** do**

**for ***j*** **←** ***i*** **+** **1** to ***n*** do**

** d **←

**return ***d*

The basic
operation of the algorithm is computing the square root. In the age of
electronic calculators with a square-root button, one might be led to believe
that computing the square root is as simple an operation as, say, addition or
multiplication. Of course, it is not. For starters, even for most integers,
square roots are irrational numbers that therefore can be found only
approximately. Moreover, computing such approximations is not a trivial matter.
But, in fact, computing square roots in the loop can be avoided! (Can you think
how?) The trick is to realize that we can simply ignore the square-root
function and compare the values ** (x_{i}
**−

Then the
basic operation of the algorithm will be squaring a number. The number of times
it will be executed can be computed as follows:

Of
course, speeding up the innermost loop of the algorithm could only de-crease
the algorithm’s running time by a constant factor (see Problem 1 in this
section’s exercises), but it cannot improve its asymptotic efficiency class. In
Chap-ter 5, we discuss a linearithmic algorithm for this problem, which is
based on a more sophisticated design technique.

**Convex-Hull
Problem**

On to the
other problem—that of computing the convex hull. Finding the convex hull for a
given set of points in the plane or a higher dimensional space is one of the
most important—some people believe the most important—problems in
com-putational geometry. This prominence is due to a variety of applications in
which this problem needs to be solved, either by itself or as a part of a
larger task. Sev-eral such applications are based on the fact that convex hulls
provide convenient approximations of object shapes and data sets given. For
example, in computer an-imation, replacing objects by their convex hulls speeds
up collision detection; the same idea is used in path planning for Mars mission
rovers. Convex hulls are used in computing accessibility maps produced from
satellite images by Geographic Information Systems. They are also used for
detecting outliers by some statisti-cal techniques. An efficient algorithm for
computing a diameter of a set of points, which is the largest distance between
two of the points, needs the set’s convex hull to find the largest distance
between two of its extreme points (see below). Finally, convex hulls are
important for solving many optimization problems, because their extreme points
provide a limited set of solution candidates.

We start
with a definition of a convex set.

**DEFINITION
**A set of
points (finite or infinite) in the plane is called** ***convex*** **if** **for any two points ** p** and

All the
sets depicted in Figure 3.4a are convex, and so are a straight line, a
triangle, a rectangle, and, more generally, any convex polygon,^{1} a
circle, and the entire plane. On the other hand, the sets depicted in Figure
3.4b, any finite set of two or more distinct points, the boundary of any convex
polygon, and a circumference are examples of sets that are not convex.

Now we
are ready for the notion of the convex hull. Intuitively, the convex hull of a
set of ** n** points in the plane is the
smallest convex polygon that contains all of them either inside or on its
boundary. If this formulation does not fire up your enthusiasm, consider the
problem as one of barricading

A formal
definition of the convex hull that is applicable to arbitrary sets, including
sets of points that happen to lie on the same line, follows.

**DEFINITION
**The** ***convex
hull*** **of a set** S **of points is the smallest convex
set

If ** S** is convex, its convex hull is
obviously

points
not on the same line, its convex hull is the triangle with the vertices at the
three points given; if the three points do lie on the same line, the convex
hull is the line segment with its endpoints at the two points that are farthest
apart. For an example of the convex hull for a larger set, see Figure 3.6.

A study
of the examples makes the following theorem an expected result.

**THEOREM **The
convex hull of any set** S **of

The ** convex-hull
problem** is the problem of constructing the convex hull for a given set

and *p*_{3}.

Extreme
points have several special properties other points of a convex set do not
have. One of them is exploited by the ** simplex method**, a very important
algorithm discussed in Section 10.1. This algorithm solves

So how
can we solve the convex-hull problem in a brute-force manner? If you do not see
an immediate plan for a frontal attack, do not be dismayed: the convex-hull
problem is one with no obvious algorithmic solution. Nevertheless, there is a
simple but inefficient algorithm that is based on the following observation
about line segments making up the boundary of a convex hull: a line segment
connecting two points ** p_{i}** and

A few
elementary facts from analytical geometry are needed to implement this
algorithm. First, the straight line through two points *(x*_{1}*, y*_{1}*), (x*_{2}*, y*_{2}** )** in the coordinate plane can be
defined by the equation

** ax **+

where ** a** =

Second,
such a line divides the plane into two half-planes: for all the points in one
of them, ** ax** +

What is
the time efficiency of this algorithm? It is in *O(n*^{3}** )**: for each of

**Exercises
3.3**

** **1. Assuming that *sqrt*
takes about 10 times longer than each of the other oper-ations in the innermost
loop of *BruteForceClosestPoints*, which
are assumed to take the same amount of time, estimate how much faster the
algorithm will run after the improvement discussed in Section 3.3.

** **2. Can you design a more efficient algorithm than the
one based on the brute-force strategy to solve the closest-pair problem for ** n** points

** **3. Let *x*_{1} *< x*_{2} *<*^{.
. .}** < x_{n}** be real
numbers representing coordinates of

**
**Design an efficient algorithm to find the
post-office location minimizing the average distance between the villages and
the post office.

**
**Design an efficient algorithm to find the
post-office location minimizing the maximum distance from a village to the post
office.

** **4. **a. **There are
several alternative ways to define a distance between two points** ***p*_{1}*(x*_{1}*, y*_{1}** ) **and

*d _{M} (p*

Prove
that ** d_{M}**
satisfies the following axioms, which every distance function must satisfy:

**
***d _{M}
(p*

**
***d _{M}
(p*

**
***d _{M}
(p*

**
**Sketch all the points in the Cartesian plane whose
Manhattan distance to the origin ** (**0

**
**True or false: A solution to the closest-pair
problem does not depend on which of the two metrics—** d_{E}**
(Euclidean) or

** **5. The ** Hamming distance** between two strings
of equal length is defined as the number of positions at which the
corresponding symbols are different. It is named after Richard Hamming
(1915–1998), a prominent American scientist and engineer, who introduced it in
his seminal paper on error-detecting and error-correcting codes.

**
**Does the Hamming distance satisfy the three axioms
of a distance metric listed in Problem 4?

**
**What is the time efficiency class of the
brute-force algorithm for the closest-pair problem if the points in question
are strings of ** m** symbols
long and the distance between two of them is measured by the Hamming distance?

** **6. *Odd pie
fight *There are* **n** *≥* *3 people
positioned on a field (Euclidean plane)* *so
that each has a unique nearest neighbor. Each person has a cream pie. At a
signal, everybody hurls his or her pie at the nearest neighbor. Assuming that ** n **is odd and that nobody can miss
his or her target, true or false: There always

7. The
closest-pair problem can be posed in the ** k**-dimensional
space, in which the Euclidean distance between two points

What is
the time-efficiency class of the brute-force algorithm for the ** k**-dimensional closest-pair
problem?

8. ** **Find the convex hulls of the following sets and
identify their extreme points (if they have any):

**a. **a line
segment

**
**a square

**
**the boundary of a square

**
**a straight line

9. ** **Design a linear-time algorithm to determine two
extreme points of the convex hull of a given set of ** n
>** 1 points in the plane.

10. ** **What modification needs to be made in the
brute-force algorithm for the convex-hull problem to handle more than two
points on the same straight line?

11. ** **Write a program implementing the brute-force
algorithm for the convex-hull problem.

12. ** **Consider the following small instance of the linear
programming problem:

**
**Sketch, in the Cartesian plane, the problem’s ** feasible
region**, defined as the set of points satisfying all the problem’s
constraints.

**
**Identify the region’s extreme points.

**
**Solve this optimization problem by using the
following theorem: A linear programming problem with a nonempty bounded
feasible region always has a solution, which can be found at one of the extreme
points of its feasible region.

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

Introduction to the Design and Analysis of Algorithms : Brute Force and Exhaustive Search : Closest-Pair and Convex-Hull Problems by Brute Force |

**Related Topics **

Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

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