### Is P monotonic in some direction?

Let **H**_{i} be the half-space determined by **{x | Ox.v**_{i}v_{i+1}>0} (where O is the origin).
The set of all directions, for which P is monotonic, is described by the intersection between D and S,
where D is the intersection of the **H**_{i} over all i, and S is the unit sphere that represents all directions in space (the sphere of directions).
Therefore we can tell P's monotonicity by checking if D is non-empty, which could be done in linear time using linear programming.

**Theorem: **Given a polygonal chain P, one can determine if P is monotonic in

**O(n)** time.

**Theorem: **Given a polygonal chain P, one can determine in **O(nlogn)** time all the directions with respect to which P is monotonic.

### How to compute all the directions with respect to which P is monotonic?

As noted above, the intersection of D and S describes the set of all the directions from which P is monotonic. The computational complexity is determined by the computing of D (the intersection of the half-spaces **H**_{i}). It could be done in **O(nlog(n))** time by the following method [3]:
Let's consider the intersection of all the H_{i}

The intersection is an associative operator, so it is equivalent to write it as

The term in parentheses on the left is an intersection of n/2 half-planes, and hence
is a convex polygonal region of at most n/2 sides. The same is true for the term on the right.
Since the intersection of two convex polygons can be performed in O(k) time, where k is the side
of each the polygon, the previous intersection can be computed in O(n) time.
This suggests the following recursive algorithm:

- Partition the half-planes in two sets of approximately equal sizes.
- Recursively form the intersection of the half-planes in each subproblem.
- Merge the subproblems solutions by intersecting the two resulting convex polygonal regions.

If **T(n)** denotes the time used to form the intersection of n half-planes by this algorithm, we have:
**T(n) = 2T(n/2) + O(n) = O(nlog(n))**.