Content

  1. Multiplication
  2. Convex Hull

Divide & Conquer

  1. Breaking problems into subproblems
  2. Recursively solving these subproblems
  3. Combining the answers
a subproblems of size n/b, combining the answers in O(n^d) time.

The k-th level of tree has a^k subproblems, each of size n/(b^k).
=> a^k * O(n/(b^k)^d) = O(n^d) * (a/(b^d))^k

=> T(n) = aT(⌈n/b⌉) + O(n^d)
        = O(n^d)           if a/(b^d) < 1
        = O((n^d)logn)       if a/(b^d) = 1
        = O(n^(log_b(a))) if a/(b^d) > 1

Multiplication

Multiply 2 n-bit integers x, y where n is a power of 2.

Steps

  1. Split x, y into halves.

    x = 2^(n/2)xl + xr
    y = 2^(n/2)yl + yr

  2. Multiplication becomes:

    xy = (2^(n/2)xl + xr) * (2^(n/2)yl + yr) = (2^n)xlyl + 2^(n/2)(xlyr + xryl) + xryr

  3. Consider:

    xlyr + xryl = (xl + xr)(yl + yr) - xlyl - xryr

  4. Multiplication becomes 3 multiplication subproblems.

Running Time

  • At depth k, there are 3^k subproblems, each of size n/(2^k)
  • 3^k * O(n/(2^k)) = (3/2)^k * O(n) at depth k
  • T(n) = 3T(n/2) + O(n) = O(n^1.59) in total

Pseudocode

Multiply(x, y):
    # Input: Positive integers x and y, in binary 
    # Output: Their product

    n = max(size of x, size of y) 
    if n = 1: 
        return xy

    xL, xR = leftmost⌈n/2⌉, rightmost⌊n/2⌋ bits of x 
    yL, yR = leftmost⌈n/2⌉, rightmost⌊n/2⌋ bits of y

    P1 = Multiply(xL, yL)
    P2 = Multiply(xR, yR)
    P3 = Multiply(xL + xR, yL + yR)
    return P1 × 2^n + (P3 − P1 −P2) × 2^(n/2) + P2

Convex Hull

  • Graham's scan: O(nlogn)

Divide and Conquer Convex Hull

  • Generalization of MergeSort

Pseudocode

# Presort points by x coordinate => O(nlogn)
# Assume linked list of hull vertices

MergeHull(HA, HB):
    Compute upper & lower tangents for HA & HB
    Discard all points lying between 2 tangents
    return MergedH

Hull(S):
    If |S| <= 3:
        Compute convex hull by brute force # => O(1)
        return H
    Else:
        Partition S into A (lowest x) & B (highest x) # => O(n)
        HA = Hull(A)
        HB = Hull(B)
        H = MergeHull(HA, HB) # => O(n)
        return H

=> 

T(n) = 1            if n <= 3
       n + 2T(n/2) otherwise

=> O(nlogn)

Computing Tangents

# Walking procedure

LowerTangent(HA, HB):
    Init a = rightmost point of HA
    Init b = leftmost point of HB

    # Orientation test of a, b, and neighboring vertices 
    While ab not a lower tangent for HA & HB:
        While ab not a lower tangent for HA:
            a = a - 1 # move clockwise
        While ab not a lower tangent for HB:
            b = b + 1 # move counterclockwise
    Return ab

=> O(|HA| + |HB|) <= O(|A| + |B|) = O(n)

Quickhull

  • Generalization of QuickSort
  • O(nlogn) ~ O(n^2)
  • No obvious way to convert it into randomized algorithm with O(nlogn) expected running time; but still performs well

Idea

  • Discard points not on the hull as quickly as possible

Steps

  1. Find max & min x, y coordinates
  2. Draw a bounding rectangle -> those lying within discarded => O(n) by now
  3. Classify remaining points into 4 corners -> if no remaining, then done
  4. For each corner, find a point c that lies on the hull. May choose c by the most perpendicular distance.
  5. Discard those in the triangle, and split remaining points into 2 subsets (classify them by 2 orientation tests).
  6. Add the 2 corners in buckets, and recurse.

Running Time

  • Depends on how evenly the points are split
    => 
T(n) = 1              if n = 1
       T(n1) + T(n2) where n1 + n2 <= n

=> O(nlogn) if evenly distributed (n1 ~= n2; max(n1, n2) <= a * n for some constant a < 1)
=> O(n^2) otherwise

Gift Wrapping and Jarvis's March

  • Variation of SelectionSort
  • O(n^2)

Steps

  1. Find any point on convex hull, e.g. lowest point
  2. Say start with p(0) = (Inf, 0), p(1) = lowest point
  3. Assume p(k) & p(k-1) were the last 2 points added, find the next one q s.t. angle[p(k-1), p(k), q] is maximized => O(n)
  4. Repeat h times, return back to starting point

Running Time

O(nh), where n is the input size, h is the output size

  • If h = o(logn), then faster than Graham's!

Chan's Algorithm

  • Combination of Graham's scan & Jarvis's march
  • Aims to be O(nlogh) (lower bound)

Steps

  1. Partition points into groups of equal size m points, total r groups
  2. For each group, compute its hull using Graham's scan => total O(rmlogm) = O(nlogm)
  3. Run Jarvis's march on the groups. Computing tangent between a point & a convex m takes O(logm) time (binary search)
    => total O(rlogm) for r groups
    => h steps of Jarvis's march, total O(hrlogm) time
  4. Combining, we get O((n + hn/m) logm) time
  5. If set m = h, running time O(nlogh)

Tricks

  • How do we know what m is if we don't know h in advance?
    • Guess the value: try m = 1, 2, ..., until m >= h => too long!
    • Binary search => but if m = n/2, stuck to O(nlogn) time
    • Doubling search: Start with small m and increase it rapidly (say, squaring it) => O(nlogh)

Pseudocode

PartialHull(P, m):

    Let r = ceil(n/m)
    Partition P into disjoint subsets P(1),P(2),... P(r), each of size at most m

    For i = 1 to r do:
        Compute Hull(P(i)) using Graham's scan
        Store the vertices in an ordered array

    Let p0 = (-Inf, 0)
    Let p1 be the bottommost point of P

    For k = 1 to m do: # => O(hrlogm) where we assume h = m
        For i = 1 to r do: # => O(rlogm)
            Compute point q in P(i) that maximizes the angle[p(k-1), p(k), q] # => O(logm)
        Let p(k+1) be the point q in q(1),q(2),...q(r) that maximizes the angle[p(k-1), p(k), q]
        If p(k+1) = p(1):
            Return {p(1), p(2), ... p(k)}

    Return "m was too small, try again."

Hull(P):

    For t = 1.. do: # stop when 2^2^t >= h, or t = ceil(lglgh)
        Let m = min(2^(2^t), n)
        Let L = PartialHull(P, m)
        If L != "try again":
            Return L

Running Time

The t-th iteration takes O(nlog2^2^t) = O(n*2^t) time
Sum(t = 1..lglgh) n*2^t =
    n * Sum(t = 1..lglgh) 2^t <= 
    n * 2^(1+lglgh) = 
    2nlgh = 
    O(nlogh)

References

results matching ""

    No results matching ""