Transcript Merging two upper hulls

Merging two upper hulls
• Suppose, UH(S2) has s points given in an array
according to their order on UH(S2).
• We allocate s processors and divide the points on
UH(S2) into s intervals and do a parallel search.
log s
)  O(1) time.
• We can identify the point q r in O(
i
log s
Lecture 7.2, page 1
Advanced Topics in Algorithms and Data Structures
Merging two upper hulls
• Suppose, the common tangent to UH(S1) and
UH(S2) is the line uv .
• u is on UH(S1) and v is on UH(S2) .
• If we know the line ri qr , we can say in O(1) time
whether u is above or below the line ri qr .
i
i
Lecture 7.2, page 2
Advanced Topics in Algorithms and Data Structures
Merging two upper hulls
• Suppose, there are t points on UH(S1), given in an
array according to their order on UH(S1).
• We divide these t points in t intervals, each
interval contains t points.
• We now do a parallel search in the following ways.
Lecture 7.2, page 3
Advanced Topics in Algorithms and Data Structures
Merging two upper hulls
• We allocate t s processors for the parallel search.
• Suppose ri is the boundary vertex of one of the
intervals.
• For each such ri, we can find the tangent ri qr to
UH(S2) in O(1) time using s processors.
i
Lecture 7.2, page 4
Advanced Topics in Algorithms and Data Structures
Merging two upper hulls
u is to the left of
if and only if
(along the polygonal chain of UH(S ))
is above
Lecture 7.2, page 5
Advanced Topics in Algorithms and Data Structures
Merging two upper hulls
• Hence, we can identify two boundary vertices rj
and rk such that u is above rj and below rk.
• Hence, u must be one of the t vertices in
between rj and rk.
• This computation takes O(1) time and s t  O(n)
processors.
Lecture 7.2, page 6
Advanced Topics in Algorithms and Data Structures
Merging two upper hulls
• We can do a similar computation to find a group
of s vertices on UH(S2) in which v is a member.
• This computation again takes O(1) time
and s t  O(n) processors.
Lecture 7.2, page 7
Advanced Topics in Algorithms and Data Structures
Merging two upper hulls
• Now, we have s vertices on UH(S2) and t
vertices on UH(S1) .
• There are s t  O(n) possible lines if we join one
point from UH(S1) and one point from UH(S2) .
• For each of these O(n) lines, we can check in O(1)
time whether the line is a common tangent to
UH(S1) and UH(S2) .
Lecture 7.2, page 8
Advanced Topics in Algorithms and Data Structures
Merging two upper hulls
• Suppose, uv is one such line.
• ul and ur are the two neighboring vertices of u.
Also, vl and vr are the two neighboring vertices of v.
• uv is the common tangent to both UH(S1) and
UH(S2) if all the point ul, ur, vl, vr are below uv .
Lecture 7.2, page 9
Advanced Topics in Algorithms and Data Structures
Merging two upper hulls
• For each of the O(n) lines, we can check this condition
in O(1) time.
• Hence, we can find a common tangent to UH(S1) and
UH(S2) in O(1) time and O(n) work.
• We can form another array of vertices containing the
vertices in UH(S1)  UH(S2) by deleting some parts of
the arrays of UH(S1) and UH(S2) and merging the
remaining parts.
Lecture 7.2, page 10
Advanced Topics in Algorithms and Data Structures
The convex hull algorithm
• We solve the problem through a divide and
conquer strategy.
• The depth of the recursion is O(log n) and we can
do the merging of the convex hulls at every level
of the recursion in O(1) time and O(n) work.
• Hence, the overall time required is O(log n) and
the overall work done is O(n log n) which is optimal.
• We need the CREW PRAM model due to the
concurrent reading in the parallel search algorithm.
Lecture 7.2, page 11
Advanced Topics in Algorithms and Data Structures
Intersection of half planes
• Consider a line L defined by the equation y = ax + b.
• L divides the entire plane into two half planes,
H+(L) and H-(L).
• H+(L) consists of all the points (, ) such that
  a + b.
• Similarly, H-(L) consists of all the points   a + b.
• Intuitively, H+(L) is the set of points on or above the
line L,
• And, H-(L) is the set of points on or below the line L.
Lecture 7.2, page 12
Advanced Topics in Algorithms and Data Structures
Intersection of half planes
• For a set of lines, the intersection of the positive
half planes defined by these lines is a convex
region.
• However, the intersection may or may not be
bounded.
• Our aim is to compute the boundary of the
intersection.
Lecture 7.2, page 13
Advanced Topics in Algorithms and Data Structures
Dual transform
• Let T be a transformation that maps a point
p = (a, b) into the line T(p) defined by y = ax + b.
• The reverse transformation maps the line
L : y = ax + b into the point T(L) = (-a, b).
Lecture 7.2, page 14
Advanced Topics in Algorithms and Data Structures
A property
Property: A point p is below a line L if and only if
T(p) is below the point T(L).
– Consider a set of lines L1, L2,…,Ln, and the region C
defined by 1 i  n H+(Li)
– The region C consists of all the points above all the lines
Li,1  i  n
Lecture 7.2, page 15
Advanced Topics in Algorithms and Data Structures
Intersection of half planes
• In the transformed domain, T(C+) = { T(p) | pC+ }
consists of all the lines above all the points T(Li),
for 1  i  n.
Lecture 7.2, page 16
Advanced Topics in Algorithms and Data Structures
Intersection of half planes
• The extreme points of the intersection of half
planes are now the line segments between two
consecutive vertices of the convex hull in the dual
space.
Lecture 7.2, page 17
Advanced Topics in Algorithms and Data Structures
Intersection of half planes
• To compute the intersection of the half planes,
we first convert the lines into their dual points.
• Then we compute the convex hull of these dual
points.
• Finally, we get the extreme points of the
intersection of half planes by converting the line
segments between two consecutive extreme
points of the convex hull into points.
Lecture 7.2, page 18
Advanced Topics in Algorithms and Data Structures
Intersection of half planes
• The transformations take O(1) time each if
we allocate one processor for each line.
• The convex hull construction takes O(log n)
time and O(n log n) work on the CREW
PRAM.
Lecture 7.2, page 19
Advanced Topics in Algorithms and Data Structures
Two variable linear program
• The two-variable linear program problem is
defined as:
Minimize cx + dy (Objective function)
Subject to: aix + biy + ci  0, 1  i  n.
(Constraints)
Lecture 7.2, page 20
Advanced Topics in Algorithms and Data Structures
Two variable linear
programming
• Each constraint is a half plane. The
feasible region is a set of points satisfying
all the constraints.
• The solution of the linear program is a
point in the feasible region that minimizes
the objective function.
• The objective function is minimized at one
of the extreme points of the feasible region.
Lecture 7.2, page 21
Advanced Topics in Algorithms and Data Structures
Two variable linear
programming
• Hence, we can find all the O(n) extreme
points of the feasible region by the half
plane intersection algorithm.
• Then we can find the extreme point which
minimizes the objective function.
• The algorithm takes O(log n) time and
O(n log n) work on the CREW PRAM.
Lecture 7.2, page 22
Advanced Topics in Algorithms and Data Structures