Transcript Microsoft PowerPoint Presentation: 07_1_Lecture

An overview of lecture 7
• An optimal parallel algorithm for the 2D
convex hull problem,
• Some applications of the 2D convex hull
algorithm.
Lecture 7.1, page 1
Advanced Topics in Algorithms and Data Structures
The convex hull problem
Input: A set S = (p1, p2,…,pn) of n points on the
plane.
Output: The convex hull CH(S) of these n
points.
• The convex hull is the smallest convex
polygon containing all the n points.
• Each vertex of CH(S) is called an extreme
point and the convex hull is output as a list
of the extreme points.
Lecture 7.1, page 2
Advanced Topics in Algorithms and Data Structures
The convex hull problem
• Let pmax and pmin be two points in the set S with the
maximum and minimum x coordinates.
• Then pmax and pmin are convex hull vertices.
• The line segment pmax pmin divides the convex hull
into two parts, upper hull and lower hull.
Lecture 7.1, page 3
Advanced Topics in Algorithms and Data Structures
The convex hull problem
• We use the notation x(p) and y(p) to denote
the x and y coordinates of a point p.
• Given a line L specified by the equation
y = ax + b, and a point q =( , ),
• We say, q is below L if  < a + b.
• We also say, q is above L if  > a + b.
Lecture 7.1, page 4
Advanced Topics in Algorithms and Data Structures
The convex hull problem
• Given the set S of n points, we can find pmax and
pmin in O(n) time.
• We can find all the points above and below pmax pmin
also in O(n) time.
• We can compute the convex hull of all the points
above pmax pmin and call this as UH(S).
• Similarly, we can compute the convex hull of all
the points below pmax pmin and call this as LH(S).
• At the end, we can stitch these two hulls together
at the two points pmax and pmin.
Lecture 7.1, page 5
Advanced Topics in Algorithms and Data Structures
Sequential complexity
• The convex hull of n planar points can be
constructed in (n log n) time sequentially.
• The lower bound can be proved by
showing that the convex hull problem is
equivalent to sorting.
• We need to design an O(n log n) work
algorithm to achieve optimality.
Lecture 7.1, page 6
Advanced Topics in Algorithms and Data Structures
Computing the upper hull
• We will discuss an algorithm for computing the
upper hull of the set S. The algorithm for
computing the lower hull is exactly the same.
• A line L is tangent to a convex polygon P if all the
vertices of P are on the same side of L.
Lecture 7.1, page 7
Advanced Topics in Algorithms and Data Structures
A divide-and-conquer algorithm
• We discuss a divide-and-conquer
algorithm for computing the upper hull.
There are two phases, top-down and
bottom-up.
• First, we sort the points according to xcoordinates.
Lecture 7.1, page 8
Advanced Topics in Algorithms and Data Structures
A divide-and-conquer algorithm
• In the top-down phase, we divide the point
set recursively into two parts and compute
the convex hull when the size of each
subproblem is small.
• In the bottom-up phase, we merge these
hulls pairwise to get the upper hull.
• The strategy is exactly similar to the
sequential algorithm for merge sort.
Lecture 7.1, page 9
Advanced Topics in Algorithms and Data Structures
A divide-and-conquer algorithm
Lecture 7.1, page 10
Advanced Topics in Algorithms and Data Structures
Merging two upper hulls
• The main problem in combining two upper hulls
to form a single upper hull is to compute a
common tangent to the two hulls.
• To achieve O(n log n) work, we need to complete
the merging of all the upper hulls at a level of the
tree in O(1) time.
Lecture 7.1, page 11
Advanced Topics in Algorithms and Data Structures
Merging two upper hulls
• We consider two upper hulls UH(S1) and UH(S2).
• Our aim is to find a common tangent to these two
upper hulls.
• We first find a tangent to UH(S2) from a point ri on
UH(S1).
Lecture 7.1, page 12
Advanced Topics in Algorithms and Data Structures
Merging two upper hulls
• Suppose the line ri qr is the tangent to UH(S2) from ri.
• Suppose ql is another vertex of UH(S2).
• Given the line riql, we first try to locate q r .
i
i
Lecture 7.1, page 13
Advanced Topics in Algorithms and Data Structures
Merging two upper hulls
• In O(1) time, we can say whether q r is above or
below the line rq
i l .
• If the neighboring vertices ql -1 and ql +1 of ql are
q r is above ql.
on either side of rq
,
then
i l
i
i
Lecture 7.1, page 14
Advanced Topics in Algorithms and Data Structures
Parallel search algorithm
• For each of the p + 1 parts of the array, a processor
checks whether y < xl, where xl is the last element of
the part.
• If y < xl, the subarray to the right of xl can be rejected.
If y > xl, the subarray to the left of xl can be rejected.
• In each iteration we identify only one subarray for
further search.
Lecture 7.1, page 15
Advanced Topics in Algorithms and Data Structures
Complexity of parallel searching
• We need to analyze what is the complexity of
reducing the size of the array to p.
• At the first iteration, we are reducing the size of
the array from n to n/p.
• Suppose, the size reduces to p after k iterations.
n
• Hence, p  p , which implies n = pk +1.
log n
k

O
(
) . We need the CREW PRAM model.
•
log p
k
Lecture 7.1, page 16
Advanced Topics in Algorithms and Data Structures