Parallel Algorithms for the Convex Hull Problem

John Daigle

Georgia State University

Overview

Introduction to the Problem

• What is the Convex Hull Problem?
• Sequential Algorithm for Convex Hull
• PRAM Algorithm

Using the Bridging Model

• What is the BSP model?
• BSP algorithm for Convex Hull

Definitions

Convex

A subset Q of the plane is convex if and only if:
&forall p, q &isin Q, line seqment pq is completely contained in Q

Convex Hull

The smallest convex set containing Q, denoted as CH(Q)

Sequential Algorithm

The Divide and Conquer Approach

Given a set of points in d dimensional Euclidian Space E^d

Algorithm CH
Input: A set S{a₁,..., a_n}, where a_i&isin E^d and x_i(a_i) < x_j(a_j)for i, j = 1,..., n.
Output: The Convex Hull CH(S)of S

1. Subdivide S into S₁ = {a₁,..., a_{&lfloor½n&rfloor}} and S₂ = {a_{&lfloor½n&rfloor+1},..., a_n}
2. Apply recursively CH to S₁ and S₂ to obtain CH(S₁) and CH(S₂)
3. Apply a merge algorithm to CH(S₁) and CH(S₂) to obtain CH(S) and halt.

Sequential Algorithm

The Divide and Conquer Approach

Analysis

• Running time
  1. The sorting operation (Step One) runs in O(nlogn) time
     
  2. The merge operation runs in linear time.
  3. Therefore the linear algorithm is O(nlogn)

The PRAM algorithm

PRAM CH(n, Q, CH(Q))

1. Sort the points of Q by their xcoordinates
2. Partition Q into n^½ subsets Q₁,Q₂, ... Q_n^½
3. FOR i = 1 to n^½ do in parallel

IF points in Q_i &le 3 THEN CH(Q_i)=Q_i
ELSE PRAM CH(n^½,Q_i,CH(Q_i))
4. CH(Q) &larr Q₁ &cup Q₂, Q₃, &cup ... &cup Q_n^½

The PRAM algorithm

The PRAM algorithm is initially quite simple. The points are sorted in increasing order by x coordinate. Then, the Set is partitioned into n^½ subsets, Q₁,Q₂, Q₃, ... Q_n^½, such that for all q_i &isin Q_i, &forall q_j&isin Q_j, the x coordinate of q_i < x of q_j.

The PRAM algorithm

Step 3 is the recursive step that finds the hull, when |Q_i| &le 3, this group is returned as the convex hull of Q_i, that is, in a group of 3 or fewer points, all of the points are in the hull.

Merging a Set of Disjoint Polygons

The Convex Hull consists of two parts:

• The Upper Hull: The sequence clockwise from u to v
• The Lower Hull: The sequence clockwise from v to u

Identifying the Upper Hull

• Suppose that n processors are available
• We assign n^½-1 processors to CH(Q_i) for i=1, 2,...,n^½
• Each processor assigned to CH(Q_i) finds the upper tangent common to CH(Q_i) and one of the remaining n^½-1 convex polygons CH(Q_j), j &ne i
• These computations are done simultaneously for all CH(Q_i), each yielding a list of points of Q on the upper hull.
• The lists are then compressed into one list using an array-packing algorithm.

Identifying the Upper Hull

Identifying a Tangent

A tangent between two polygon a and b is a line which runs through a single point k of a and a single point m of b without passing through either a or b.

To compute a tangent between CH(Q_i) and CH(Q_j), we select a point in the middle of the sequence from u to v of both Q_i and Q_j (the midpoint of the upper hull of each polygon). For Q_i call this s, and w for Q_j

1. Either (s,w) is the upper common tangent of CH(Q_i) and CH(Q_j), in which case we are done.
2. Or we can eliminate one half of the remaining corners of CH(Q_i) and CH(Q_j) as candidates for k, m

Identifying a Tangent

Simple cases of tangents and rules for elimination.

Analysis of the PRAM algorithm

• Step One: Sorting
  Given n processors, PRAM SORT is O(logn).
• Step Two: Partitioning
  O(1) for n processors to partition n points.
• Step Three: Recursive Step
  t(n^½), where t(n) is the running time for the Algorithm PRAM CONVEX HULL, and n^½ processors compute CH(Q_i)

Analysis of the PRAM algorithm

• Step Four: Merging
  • Each of (n^½-1)n^½ processors computes one tangent in O(logn) time, similar to a binary search.
  • Tangents L_i and R_i are found in constant time using a MIN CW instruction for each CH(Q_i).
  • Determining whether the corners from l_i to r_i belong to the upper hull is done in constant time.
  • Array packing is O(logn)
• The entire algorithm is therefore:
  t(n) = t(n^½) + &beta logn
  t(n) = O(logn).
• This is optimal, as convex hull is bounded by search.

The Bridging Model

• In sequential computing, one unifying model, the RAM architecture.
• In parallel computing, the PRAM machine comes in many flavors and topologies.
• A bridging model for parallel programming would provide a unifying model for all of these.

The Bridging Model

• What are the advantages of a bridging model?
• What are the challenges?
  • Maintaining efficiency.
  • Sufficient generality.
• Bulk-Synchronous Parallel model.
  1. A number of components, processors and/or memory
  2. A router that delivers messages point to point between components.
  3. Facilities for synchronizing a subset of the components at regular intervals of L time units.

BSP supersteps

• A computation is divided into supersteps.
• Each component is allocated a task
  • 1 or more local computation steps
  • 1 or more message transmissions
• Periodic global checks are made to determine wether the current step is complete. If yes, the machine proceeds to the next superstep, if no, the next period of L units is allocated to the current superstep.
• The total run time of a BSP algorithm is the sum of the computation time plus the total communication time.

BSP Terms

A BSP Communication is described by

O(T₁ + (L + gh)T_C)

• T₁ is the total computation time
• L is the Latency of the network
• g is the intrastep gap between messages
• h is the number of messages usually &Theta(n/p)
• T_C is the number of communication rounds.