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.[1]
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.
Properties
[edit]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.
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
[edit]Sweepable polygons
[edit]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
[edit]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.
See also
[edit]- 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 polygons, a polar coordinates analog of monotone polygons
References
[edit]- ^ a b 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.
- ^ a b 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.
- ^ a b 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.