find the smallest convex polygon that contains n given points in the plane. We consider here a divide-and-conquer algorithm called quickhull because of its resemblance to quicksort.

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

In Section 3.3, 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

Let us
revisit the convex-hull problem, introduced in Section 3.3: find the smallest
convex polygon that contains ** n** given
points in the plane. We consider here a divide-and-conquer algorithm called

Let ** S** be a set of

The
boundary of the convex hull of ** S** is made
up of two polygonal chains: an “upper” boundary and a “lower” boundary. The
“upper” boundary, called the

For
concreteness, let us discuss how quickhull proceeds to construct the upper
hull; the lower hull can be constructed in the same manner. If *S*_{1} is
empty, the

upper
hull is simply the line segment with the endpoints at *p*_{1} and ** p_{n}.** If

Therefore,
the algorithm can continue constructing the upper hulls of *p*_{1} ∪ *S*_{1}_{,}_{1}** **∪

Now we
have to figure out how the algorithm’s geometric operations can be actually
implemented. Fortunately, we can take advantage of the following very useful
fact from analytical geometry: if *q*_{1}*(x*_{1}*, y*_{1}*), q*_{2}*(x*_{2}*, y*_{2}** ),** and

while the
sign of this expression is positive if and only if the point *q*_{3} = *(x*_{3}*, y*_{3}** )** is to

−−−→

the left
of the line *q*_{1} *q*_{2} ** .** Using this formula, we can check
in constant time whether a point lies to the left of the line determined by two
other points as well as find the distance from the point to the line.

Quickhull
has the same * (n*^{2}** )** worst-case efficiency as
quicksort (Problem 9 in this section’s exercises). In the average case,
however, we should expect a much better performance. First, the algorithm
should benefit from the quicksort-like savings from the on-average balanced
split of the problem into two smaller subproblems. Second, a significant
fraction of the points—namely, those inside

**Exercises
5.5**

**
****a. **For the
one-dimensional version of the closest-pair problem, i.e., for the** **problem of finding two closest numbers
among a given set of ** n** real
num-bers, design an algorithm that is directly based on the divide-and-conquer
technique and determine its efficiency class.

**b. **Is it a good algorithm for this
problem?

**
**Prove that the divide-and-conquer algorithm for the
closest-pair problem examines, for every point ** p** in the
vertical strip (see Figures 5.7a and 5.7b), no more than seven other points
that can be closer to

**
**Consider the version of the divide-and-conquer
two-dimensional closest-pair algorithm in which, instead of presorting input
set ** P** , we simply sort each of the two
sets

Implement
the divide-and-conquer closest-pair algorithm, outlined in this section, in the
language of your choice.

**
**Find on the Web a visualization of an algorithm for
the closest-pair problem. What algorithm does this visualization represent?

**
**The **Voronoi
polygon** for a point ** p** of a set

**
**What is the Voronoi diagram for a set of three
points?

**
**Find a visualization of an algorithm for generating
the Voronoi diagram on the Web and study a few examples of such diagrams. Based
on your observations, can you tell how the solution to the previous question is
generalized to the general case?

**
**Explain how one can find point *p*_{max} in the
quickhull algorithm analytically.

**
**What is the best-case efficiency of quickhull?

**
**Give a specific example of inputs that make
quickhull run in quadratic time.

**
**Implement quickhull in the language of your choice.

**
***Creating
decagons *There are 1000 points in the plane, no three of them* *on the same line. Devise an algorithm to construct 100 decagons
with their vertices at these points. The decagons need not be convex, but each
of them has to be simple, i.e., its boundary should not cross itself, and no
two decagons may have a common point.

*Shortest path around *There is
a fenced area in the two-dimensional Eu-clidean plane in the shape of a convex
polygon with vertices at points *p*_{1}*(x*_{1}*, y*_{1}*), p*_{2}*(x*_{2}*, y*_{2}** ), . . . , p_{n}(x_{n}, y_{n})
**(not
necessarily in this order). There are

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

Introduction to the Design and Analysis of Algorithms : Divide and Conquer : Convex Hull Problems 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.