Reporting Intersection

of a Set of Half Planes

 

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

 

 

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.