Monotone polygon

Monotone polygons are defined with respect to a straight line \( L \), where every orthogonal line intersects the polygon's boundary at most twice or its chain at most once. For practical purposes, this definition can be extended to allow edges orthogonal to \( L \). A convex polygon is monotone in any direction, and if a polygon is monotone in all directions, it is convex.

Properties include that the leftmost and rightmost vertices of a monotone polygon (with \( L \) as the x-axis) divide its boundary into two chains with monotonically increasing or decreasing X-coordinates. Point-in-polygon queries can be answered efficiently after preprocessing. Monotone polygons can be triangulated in linear time, and minimal bitonic tours for point sets exist.

Cutting a simple polygon into monotone polygons can be done in \( O(n \log n) \) time, though triangle-based triangulation is more efficient with complex or randomized algorithms. Minimal uniformly monotone decompositions are solvable in polynomial time. Motion planning benefits from the separability of non-intersecting monotone polygons via translation.

Generalizations include sweepable polygons, recognized in quadratic time, and 3D polyhedrons classified as weakly monotonic or convex based on cross-sections. Other concepts like orthogonal convexity and star-shaped polygons are related.