monotone polygon

A monotone polygon may be easily triangulated in linear time.

A simple polygon may be decomposed into monotone polygons as follows.

A monotone polygon is sweepable by a line which does not change its orientation during the sweep.

In fact, this property may be taken for the definition of monotone polygon and it gives the polygon its name.

For a given set of points in the plane, a bitonic tour is a monotone polygon that connects the points.

A simple polygon may be easily cut into monotone polygons in O(n log n) time.

When the input is a monotone polygon, its straight skeleton can be constructed in time O(n log n).

Compare with "Monotone polygon".

Boolean operations on convex polygons and monotone polygons of the same direction may be performed in linear time.

Simpler algorithms are possible for monotone polygons, star-shaped polygons and convex polygons.

Cutting a simple polygon into the minimal number of uniformly monotone polygons (i.e., monotone with respect to the same line) can be performed in polynomial time.

The bitonic tour of a set of points is the minimum-perimeter monotone polygon that has the points as its vertices; it can be computed efficiently by dynamic programming.

Point in polygon queries with respect to a monotone polygon may be answered in logarithmic time after linear time preprocessing (to find the leftmost and rightmost vertices).

However since a triangle is a monotone polygon, polygon triangulation is in fact cutting a polygon into monotone ones, and it may be performed in O(n) time.

A monotone polygon with respect to a line L is a polygon with the property that every line orthogonal to L intersects the polygon in a single interval.

A monotone polygon can easily be triangulated in linear time with either the algorithm of A. Fournier and D.Y. Montuno, or the algorithm of Godfried Toussaint.

Then the leftmost and rightmost vertices of a monotone polygon decompose its boundary into two monotone polygonal chains such that when the vertices of any chain are being traversed in their natural order, their X-coordinates are monotonically increasing or decreasing.

In the context of motion planning, two nonintersecting monotone polygons are separable by a single translation (i.e., there exists a translation of one polygon such that the two become separated by a straight line into different halfplanes) and this separation may be found in linear time.