Divide and Conquer

This is a basic problem solving technique and has proven to be very useful for geometric problems as well. This technique mainly involves partitioning of the given problem into several subproblems, recursively solving each subproblem, and then combining the solutions to each of the subproblems to obtain the final solution to the optimal problem.

We demonstrate its working by considering the problem of computing the common intersection of $n$ half planes in the plane. Given is the set $S$ of $n$ half-planes, $h_i$, represented by,

$$a_i x + b_i y \leq c_i, i=1, 2, \dots, n.$$ (3.1)

Example 3.1   Let for $i=1$, $h_1$ is: $5x + 4y \geq 20$. This gives all points in half plane as shown in figure .

Figure: Half plane $5x + 4y \geq 20$.

It is simple to understand that, common intersection of half-planes, denoted by,

$$C(S) = \bigcap_{i=1}^n h_i$$ (3.2)

is a convex set, which may or may not be bounded. If it is bounded, it is convex polygon. In figure  the shaded area is common intersection.

The divide and conquer algorithm computes the following steps:

Figure: Divide-and-conquer scheme for common intersecting half-planes(half planes are on the side of arrows).

The key step is the merge of two common intersections. Because CI($S_1$) and CI($S_2$) are convex, the merge step basically calls for the computation of the intersection of two convex polygons, which can be solved in time proportional to the size of the polygons. The running time of D&C algorithm is $O(n \log n)$ due to following recurrence formula, where $n = \vert S\vert$.

	$$T(3)$$	$$= O(1)\nonumber$$
	$$T(n)$$	$$= 2T\left(\frac{n}{2}\right) + O(n) + M\left( \frac{n}{2}, \frac{n}{2}\right),\nonumber$$

where, $M\left(\frac{n}{2}, \frac{n}{2}\right) = O(n)$ denotes the merge time (step 5).