In geometry

Geometry

Geometry arose as the field of knowledge dealing with spatial relationships. Geometry was one of the two fields of pre-modern mathematics, the other being the study of numbers ....

, a polygon

Polygon

In geometry a polygon is a flat shape consisting of straight lines that are joined to form a closed chain orcircuit.A polygon is traditionally a plane figure that is bounded by a closed path, composed of a finite sequence of straight line segments...

P in the plane is called monotone with respect to a straight line L, if every line orthogonal to L intersects P at most twice.

Similarly, a polygonal chain

Polygonal chain

A polygonal chain, polygonal curve, polygonal path, or piecewise linear curve, is a connected series of line segments. More formally, a polygonal chain P is a curve specified by a sequence of points \scriptstyle called its vertices so that the curve consists of the line segments connecting the...

 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

Simple polygon

In geometry, a simple polygon is a closed polygonal chain of line segments in the plane which do not have points in common other than the common vertices of pairs of consecutive segments....

 may be called monotone, if a line segment that connects two points in P and is orthogonal to L completely belongs to P.

Following the terminology for monotone functions, the former definition describes polygons strictly monotone with respect to L. The "with respect to" part is necessary for drawing the strict/nonstrict distinction: a polygon nonstrictly monotone with respect to L is strictly monotone with respect to a line L₁ rotated from L by a sufficiently small angle.

Properties

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 chain

Polygonal chain

A polygonal chain, polygonal curve, polygonal path, or piecewise linear curve, is a connected series of line segments. More formally, a polygonal chain P is a curve specified by a sequence of points \scriptstyle called its vertices so that the curve consists of the line segments connecting the...

s 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

Convex polygon

In geometry, a polygon can be either convex or concave .- Convex polygons :A convex polygon is a simple polygon whose interior is a convex set...

 is monotone with respect to any straight line.

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

Point in polygon

In computational geometry, the point-in-polygon problem asks whether a given point in the plane lies inside, outside, or on the boundary of a 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

Polygon triangulation

In computational geometry, polygon triangulation is the decomposition of a polygonal area P into a set of triangles, i.e., finding the set of triangles with pairwise non-intersecting interiors whose union is P....

 in linear time.

For a given set of points in the plane, a bitonic tour

Bitonic tour

In computational geometry, a bitonic tour of a set of point sites in the Euclidean plane is a closed polygonal chain that has each site as one of its vertices, such that any vertical line crosses the chain at most twice....

 is a monotone polygon that connects the points. The minimum perimeter

Perimeter

A perimeter is a path that surrounds an area. The word comes from the Greek peri and meter . The term may be used either for the path or its length - it can be thought of as the length of the outline of a shape. The perimeter of a circular area is called circumference.- Practical uses :Calculating...

 bitonic tour for a given point set with respect to a fixed direction may be found in polynomial time using dynamic programming

Dynamic programming

In mathematics and computer science, dynamic programming is a method for solving complex problems by breaking them down into simpler subproblems. It is applicable to problems exhibiting the properties of overlapping subproblems which are only slightly smaller and optimal substructure...

. It is easily shown that such a minimal bitonic tour is a simple polygon: a pair of crossing edges may be replaced with a shorter non-crossing pair while preserving the bitonicity of the new tour.

A simple polygon may be easily cut into monotone polygons in O(n log n) time. However since a triangle is a monotone polygon, polygon triangulation

Polygon triangulation

In computational geometry, polygon triangulation is the decomposition of a polygonal area P into a set of triangles, i.e., finding the set of triangles with pairwise non-intersecting interiors whose union is P....

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

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.

In the context of motion planning

Motion planning

Motion planning is a term used in robotics for the process of detailing a task into discrete motions....

, 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.

Sweepable polygons

A polygon is called sweepable, if a straight line may be continuously moved over the whole polygon in such a way that at any moment its intersection with the polygonal area is a convex set. A monotone polygon is sweepable by a line which does not change its orientation during the sweep. A polygon is strictly sweepable if no portion of its area is swept more than once. Both types of sweepability are recognized in quadratic time.

3D

There is no single straightforward generalization of polygon monotonicity to higher dimensions.

In one approach the preserved monotonicity trait is the line L. A three-dimensional polyhedron is called weakly monotonic in direction L if all cross-sections orthogonal to L are simple polygons. If the cross-sections are convex, then the polyhedron is called weakly monotonic in convex sense. Both types may be recognized in polynomial time.

In another approach the preserved one-dimensional trait is the orthogonal direction. This gives rise for the notion of polyhedral terrain in three dimensions: a polyhedral surface with the property that each vertical (i.e., parallel to Z axis) line intersects the surface at most by one point or segment.

See also

• Orthogonal convexity, for polygons which are monotone simultaneously with respect to two mutually orthogonal directions; also a generalization for any number of fixed directions.
• Star-shaped polygon
  Star-shaped polygon
  A star-shaped polygon is a polygonal region in the plane which is a star domain, i.e., a polygon P is star-shaped, if there exists a point z such that for each point p of P the segment zp lies entirely within P.The set of all points z with the described property is called the kernel of...
  
  s, a polar coordinates analog of monotone polygons