next up previous

Next: Trees Up: Monotonicity Issues Previous: Monotonicity Issues

Polygonal Chains

Let's start with a polygonal chain, and a direction d.

Observation: A polygonal chain is monotonic in direction d, if the intersection of P with every plane perpendicular to d is empty or a single point.

Is P monotonic in direction d?

First consider a single segment [ab]. It is monotonic in every direction except those perpendicular to the line segment. Here we are interested in the oriented direction d for whose d.ab>0 (a dot between two vectors denotes dot product, same hereafter).

Let's adopt a new convention:
If P is monotonic with respect to d then v1 (first vertex of P) is a minimum for P with respect to d. For example, if we consider the line segment [ab], a is minimum for all directions d with d.ab>0.

Now consider the whole polygon P, it is monotonic with respect to d if every line segment of P, [v1 v2][v2v3]... [vn-1vn] is monotonic with respect to d. Thus for every i between 1 and n-1, we just need to check every product vivi+1.d>0.

Theorem: Given a polygonal chain P and a direction d, one can determine if P is monotonic with respect to d in O(n) time.

Is P monotonic in some direction?

Let Hi be the half-space determined by {x | Ox.vivi+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 Hi 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 Hi). It could be done in O(nlog(n)) time by the following method [3]:

Let's consider the intersection of all the Hi

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:

  1. Partition the half-planes in two sets of approximately equal sizes.
  2. Recursively form the intersection of the half-planes in each subproblem.
  3. 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)).

next up previous

Contact us :

Jean HERBIERE and Yueyun SHU