Divide-and-Conquer Strategy

The algorithm for reporting the intersection of a set of half planes uses the divide-and-conquer strategy. This strategy relies on a recursive approach and has two steps. The top down step, the input is recursively divided until the subproblems are small enough to be solved easily. The Bottom-up step consists of recursively merging the solutions. A divide-and-conquer algorithm can be thought of as a binary tree, where the leaves correspond to “atomic” operations and the nodes to merge operations.

For simplicity, assume that the resultant polygon is convex and we know how to search the space R, which is a rectangle. The resulting polygon contains in R i.e., rectangle.

The divide-and-conquer strategy can be describe in three steps as follows

• Build the structure
      The set of n half-planes in the input is recursively halved until we obtain n single half-plane (Note that this yields a binary tree).
• Solve an atomic problem
      The half-plane in each leaf node is intersected with rectangle R (i.e., search space). This yields a convex polygon in each leaf.
• Merge the results
      Compute recursively the intersection of convex polygon in bottom-up fashion.

Merging Step

The binary tree is processed bottom up as follows. At each node of the tree, compute intersection of two convex polygons. If p and p` are the number of vertices of two polygons to be intersected, convex polygon intersection is linear i.e., O(p + p`). The merging step eventually delivers a convex polygon that is the intersection (if any) of the n half-planes.

Algorithm

The recursive algorithm is as follows: Suppose S be the set of half-planes.

HALF-PLANE-INTERSECTION (S)

If |S| > 2 then
    Compute :  HALF-PLANE-INTERSECTION (S/2) ∩ HALF-PLANE-INTERSECTION (S-S/2)
Else
    return S ∩ R

Complexity

The time complexity of HALF-PLANE-INTERSECTION algorithm is O(n log n). One can show that the algorithm for half-plane intersection is optimal since sorting problem can be reduced to the half-plane intersection problem.