Monotone polygon

Last updated November 10, 2024

Lines orthogonal to L:
.mw-parser-output .legend{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .legend-color{display:inline-block;min-width:1.25em;height:1.25em;line-height:1.25;margin:1px 0;text-align:center;border:1px solid black;background-color:transparent;color:black}.mw-parser-output .legend-text{}
1 intersection
2 intersections
3+ intersections
The top two polygons are monotone with respect to L while the bottom two are not. M-polygon.svg — Lines orthogonal to $L$ :
  1 intersection
  2 intersections
  3+ intersections
The top two polygons are monotone with respect to $L$ while the bottom two are not.

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.^[1]

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 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.^[2] It was generalized to report all ways to decompose a simple polygon into two monotone chains (possibly monotone in different directions.)^[3]

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).^[1]

A monotone polygon may be easily triangulated in linear time.^[4]

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.^[5] 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.

Breaking a polygon into monotone polygons Polygon-to-monotone.png — Breaking a polygon into monotone polygons

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 is in fact cutting a polygon into monotone ones, and it may be performed for simple polygons in O(n) time with a complex algorithm.^[6] A simpler randomized algorithm with linear expected time is also known.^[7]

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.^[8]

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.^[9]

Generalizations

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.^[10]

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.^[9] Both types may be recognized in polynomial time.^[10]

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.

Related Research Articles

In geometry, the convex hull, convex envelope or convex closure of a shape is the smallest convex set that contains it. The convex hull may be defined either as the intersection of all convex sets containing a given subset of a Euclidean space, or equivalently as the set of all convex combinations of points in the subset. For a bounded subset of the plane, the convex hull may be visualized as the shape enclosed by a rubber band stretched around the subset.

Computational geometry is a branch of computer science devoted to the study of algorithms which can be stated in terms of geometry. Some purely geometrical problems arise out of the study of computational geometric algorithms, and such problems are also considered to be part of computational geometry. While modern computational geometry is a recent development, it is one of the oldest fields of computing with a history stretching back to antiquity.

The point location problem is a fundamental topic of computational geometry. It finds applications in areas that deal with processing geometrical data: computer graphics, geographic information systems (GIS), motion planning, and computer aided design (CAD).

A simple polygon that is not convex is called concave, non-convex or reentrant. A concave polygon will always have at least one reflex interior angle—that is, an angle with a measure that is between 180 degrees and 360 degrees exclusive.

<span class="mw-page-title-main">Polygon triangulation</span> Partition of a simple polygon into triangles

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

In geometry, a simple polygon is a polygon that does not intersect itself and has no holes. That is, it is a piecewise-linear Jordan curve consisting of finitely many line segments. These polygons include as special cases the convex polygons, star-shaped polygons, and monotone polygons.

The art gallery problem or museum problem is a well-studied visibility problem in computational geometry. It originates from the following real-world problem:

"In an art gallery, what is the minimum number of guards who together can observe the whole gallery?"

<span class="mw-page-title-main">Straight skeleton</span> Method in geometry for representing a polygon by a topological skeleton

In geometry, a straight skeleton is a method of representing a polygon by a topological skeleton. It is similar in some ways to the medial axis but differs in that the skeleton is composed of straight line segments, while the medial axis of a polygon may involve parabolic curves. However, both are homotopy-equivalent to the underlying polygon.

A rectilinear polygon is a polygon all of whose sides meet at right angles. Thus the interior angle at each vertex is either 90° or 270°. Rectilinear polygons are a special case of isothetic polygons.

Algorithms that construct convex hulls of various objects have a broad range of applications in mathematics and computer science.

<span class="mw-page-title-main">Star-shaped polygon</span> Polygon visible from one of its points

In geometry, a star-shaped polygon is a polygonal region in the plane that is a star domain, that is, a polygon that contains a point from which the entire polygon boundary is visible.

In computational geometry, the visibility polygon or visibility region for a point $p$ in the plane among obstacles is the possibly unbounded polygonal region of all points of the plane visible from $p$ . The visibility polygon can also be defined for visibility from a segment, or a polygon. Visibility polygons are useful in robotics, video games, and in various optimization problems such as the facility location problem and the art gallery problem.

<span class="mw-page-title-main">Polygonal chain</span> Connected series of line segments

In geometry, a polygonal chain is a connected series of line segments. More formally, a polygonal chain ⁠ $⁠$ is a curve specified by a sequence of points $called its vertices. The curve itself consists of the line segments connecting the consecutive vertices.$

In computational geometry, the method of rotating calipers is an algorithm design technique that can be used to solve optimization problems including finding the width or diameter of a set of points.

In geometry, a covering of a polygon is a set of primitive units whose union equals the polygon. A polygon covering problem is a problem of finding a covering with a smallest number of units for a given polygon. This is an important class of problems in computational geometry. There are many different polygon covering problems, depending on the type of polygon being covered. An example polygon covering problem is: given a rectilinear polygon, find a smallest set of squares whose union equals the polygon.

In geometry, a partition of a polygon is a set of primitive units, which do not overlap and whose union equals the polygon. A polygon partition problem is a problem of finding a partition which is minimal in some sense, for example a partition with a smallest number of units or with units of smallest total side-length.

In geometry, the two ears theorem states that every simple polygon with more than three vertices has at least two ears, vertices that can be removed from the polygon without introducing any crossings. The two ears theorem is equivalent to the existence of polygon triangulations. It is frequently attributed to Gary H. Meisters, but was proved earlier by Max Dehn.

In computational geometry, a fan triangulation is a simple way to triangulate a polygon by choosing a vertex and drawing edges to all of the other vertices of the polygon. Not every polygon can be triangulated this way, so this method is usually only used for convex polygons.

In discrete geometry and computational geometry, the convex hull of a simple polygon is the polygon of minimum perimeter that contains a given simple polygon. It is a special case of the more general concept of a convex hull. It can be computed in linear time, faster than algorithms for convex hulls of point sets.

In computational geometry, a polygonalization of a finite set of points in the Euclidean plane is a simple polygon with the given points as its vertices. A polygonalization may also be called a polygonization, simple polygonalization, Hamiltonian polygon, non-crossing Hamiltonian cycle, or crossing-free straight-edge spanning cycle.

References

1 2 Preparata, Franco P.; Shamos, Michael Ian (1985), Computational Geometry – An Introduction , Springer-Verlag, ISBN 0-387-96131-3, 1st edition; 2nd printing, corrected and expanded, 1988:; Russian translation, 1989
↑ Preparata, Franco P.; Supowit, Kenneth J. (1981), "Testing a simple polygon for monotonicity", Information Processing Letters , 12 (4): 161–164, doi:10.1016/0020-0190(81)90091-0 .
↑ Rappaport, David; Rosenbloom, Arnold (1994), "Moldable and castable polygons", Computational Geometry, 4 (4): 219–233, doi: 10.1016/0925-7721(94)90020-5 .
↑ Fournier, A.; Montuno, D. Y. (1984), "Triangulating simple polygons and equivalent problems", ACM Transactions on Graphics , 3 (2): 153–174, doi: 10.1145/357337.357341 , ISSN 0730-0301, S2CID 33344266
↑ Introduction to Algorithms , 2nd ed., T. H. Cormen, C. E. Leiserson, R. Rivest, and C. Stein, MIT Press, 2001. Problem 15-1, p. 364.
↑ Chazelle, Bernard (1991), "Triangulating a Simple Polygon in Linear Time", Discrete & Computational Geometry , 6 (3): 485–524, doi: 10.1007/BF02574703 , ISSN 0179-5376
↑ Amato, Nancy M.; Goodrich, Michael T.; Ramos, Edgar A. (2001), "A Randomized Algorithm for Triangulating a Simple Polygon in Linear Time", Discrete & Computational Geometry , 26 (2): 245–265, doi: 10.1007/s00454-001-0027-x , ISSN 0179-5376
↑ Liu, Robin (1988), "On decomposing polygons into uniformly monotone parts", Information Processing Letters , 27 (2): 85–89, doi:10.1016/0020-0190(88)90097-X .
1 2 Toussaint, G. T.; El Gindy, H. A. (1984), "Separation of two monotone polygons in linear time", Robotica, 2 (4): 215–220, doi:10.1017/S0263574700008924, S2CID 21790511 .
1 2 Bose, Prosenjit; van Kreveld, Marc (2005), "Generalizing monotonicity: On recognizing special classes of polygons and polyhedra by computing nice sweeps", International Journal of Computational Geometry & Applications, 15 (6): 591–608, doi:10.1142/S0218195905001877, hdl: 1874/24150 .

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[PS-1] 1 2 Preparata, Franco P.; Shamos, Michael Ian (1985), Computational Geometry – An Introduction , Springer-Verlag, ISBN 0-387-96131-3, 1st edition; 2nd printing, corrected and expanded, 1988:; Russian translation, 1989

[2] Preparata, Franco P.; Supowit, Kenneth J. (1981), "Testing a simple polygon for monotonicity", Information Processing Letters , 12 (4): 161–164, doi:10.1016/0020-0190(81)90091-0 .

[3] Rappaport, David; Rosenbloom, Arnold (1994), "Moldable and castable polygons", Computational Geometry, 4 (4): 219–233, doi: 10.1016/0925-7721(94)90020-5 .

[4] Fournier, A.; Montuno, D. Y. (1984), "Triangulating simple polygons and equivalent problems", ACM Transactions on Graphics , 3 (2): 153–174, doi: 10.1145/357337.357341 , ISSN 0730-0301, S2CID 33344266

[5] Introduction to Algorithms , 2nd ed., T. H. Cormen, C. E. Leiserson, R. Rivest, and C. Stein, MIT Press, 2001. Problem 15-1, p. 364.

[6] Chazelle, Bernard (1991), "Triangulating a Simple Polygon in Linear Time", Discrete & Computational Geometry , 6 (3): 485–524, doi: 10.1007/BF02574703 , ISSN 0179-5376

[7] Amato, Nancy M.; Goodrich, Michael T.; Ramos, Edgar A. (2001), "A Randomized Algorithm for Triangulating a Simple Polygon in Linear Time", Discrete & Computational Geometry , 26 (2): 245–265, doi: 10.1007/s00454-001-0027-x , ISSN 0179-5376

[8] Liu, Robin (1988), "On decomposing polygons into uniformly monotone parts", Information Processing Letters , 27 (2): 85–89, doi:10.1016/0020-0190(88)90097-X .

[telg-9] 1 2 Toussaint, G. T.; El Gindy, H. A. (1984), "Separation of two monotone polygons in linear time", Robotica, 2 (4): 215–220, doi:10.1017/S0263574700008924, S2CID 21790511 .

[bk-10] 1 2 Bose, Prosenjit; van Kreveld, Marc (2005), "Generalizing monotonicity: On recognizing special classes of polygons and polyhedra by computing nice sweeps", International Journal of Computational Geometry & Applications, 15 (6): 591–608, doi:10.1142/S0218195905001877, hdl: 1874/24150 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]