## 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

**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.