Monotone polygon

In geometry, a polygon P in the plane is called monotone with respect to a straight line L, if every line orthogonal to L intersects the boundary of P at most twice. Similarly, a polygonal chain C is called monotone with respect to a straight line L, if every line orthogonal to L intersects C at most once. For many practical purposes this definition may be extended to allow cases when some edges of P are orthogonal to L, and a simple polygon may be called monotone if a line segment that connects two points in P and is orthogonal to L lies completely in P. Following the terminology for monotone functions, the former definition describes polygons strictly monotone with respect to L. Assume that L coincides with the x-axis. 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 fact, this property may be taken for the definition of monotone polygon and it gives the polygon its name. A convex polygon is monotone with respect to any straight line and a polygon which is monotone with respect to every straight line is convex. A linear time algorithm is known to report all directions in which a given simple polygon is monotone. It was generalized to report all ways to decompose a simple polygon into two monotone chains (possibly monotone in different directions.) 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). A monotone polygon may be easily triangulated in linear time. For a given set of points in the plane, a bitonic tour is a monotone polygon that connects the points. The minimum perimeter bitonic tour for a given point set with respect to a fixed direction may be found in polynomial time using dynamic programming.