Simple Polygons

Next: Applet Up: Monotonicity Issues Previous: Trees

Simple Polygons

Observation: A simple polygon is monotonic in direction d provided there exist two vertices u, v of P that both paths from u to v are monotonic in direction d.

The characterization of monotonicity of simple polygons is similar to that of trees, thus we can apply the solution for trees to simple polygons:

Corollary: Given a simple polygon P and a direction d, it can be determined in O(n) time if P is monotonic with respect to d.

Corollary: Given a simple polygon P, in O(n²) time, we can determine all the directions with respect to which P is monotonic.

Jean HERBIERE and Yueyun SHU